/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c

Bug Summary

File:	build/gcc/loop-iv.c
Warning:	line 2442, column 7 Value stored to 'step_val' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name loop-iv.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model static -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/lib64/clang/11.0.0 -D IN_GCC -D HAVE_CONFIG_H -I . -I . -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/. -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../include -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcpp/include -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcody -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber/bid -I ../libdecnumber -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libbacktrace -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/10/../../../../include/c++/10 -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/10/../../../../include/c++/10/x86_64-suse-linux -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/10/../../../../include/c++/10/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib64/clang/11.0.0/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-narrowing -Wwrite-strings -Wno-error=format-diag -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings -fdeprecated-macro -fdebug-compilation-dir /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/gcc -ferror-limit 19 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=plist-html -analyzer-config silence-checkers=core.NullDereference -faddrsig -o /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/clang-static-analyzer/2021-01-16-135054-17580-1/report-ggfQKn.plist -x c++ /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c

1	/* Rtl-level induction variable analysis.
2	Copyright (C) 2004-2021 Free Software Foundation, Inc.
3
4	This file is part of GCC.
5
6	GCC is free software; you can redistribute it and/or modify it
7	under the terms of the GNU General Public License as published by the
8	Free Software Foundation; either version 3, or (at your option) any
9	later version.
10
11	GCC is distributed in the hope that it will be useful, but WITHOUT
12	ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14	for more details.
15
16	You should have received a copy of the GNU General Public License
17	along with GCC; see the file COPYING3. If not see
18	<http://www.gnu.org/licenses/>. */
19
20	/* This is a simple analysis of induction variables of the loop. The major use
21	is for determining the number of iterations of a loop for loop unrolling,
22	doloop optimization and branch prediction. The iv information is computed
23	on demand.
24
25	Induction variables are analyzed by walking the use-def chains. When
26	a basic induction variable (biv) is found, it is cached in the bivs
27	hash table. When register is proved to be a biv, its description
28	is stored to DF_REF_DATA of the def reference.
29
30	The analysis works always with one loop -- you must call
31	iv_analysis_loop_init (loop) for it. All the other functions then work with
32	this loop. When you need to work with another loop, just call
33	iv_analysis_loop_init for it. When you no longer need iv analysis, call
34	iv_analysis_done () to clean up the memory.
35
36	The available functions are:
37
38	iv_analyze (insn, mode, reg, iv): Stores the description of the induction
39	variable corresponding to the use of register REG in INSN to IV, given
40	that REG has mode MODE. Returns true if REG is an induction variable
41	in INSN. false otherwise. If a use of REG is not found in INSN,
42	the following insns are scanned (so that we may call this function
43	on insns returned by get_condition).
44	iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
45	corresponding to DEF, which is a register defined in INSN.
46	iv_analyze_expr (insn, mode, expr, iv): Stores to IV the description of iv
47	corresponding to expression EXPR evaluated at INSN. All registers used by
48	EXPR must also be used in INSN. MODE is the mode of EXPR.
49	*/
50
51	#include "config.h"
52	#include "system.h"
53	#include "coretypes.h"
54	#include "backend.h"
55	#include "rtl.h"
56	#include "df.h"
57	#include "memmodel.h"
58	#include "emit-rtl.h"
59	#include "diagnostic-core.h"
60	#include "cfgloop.h"
61	#include "intl.h"
62	#include "dumpfile.h"
63	#include "rtl-iter.h"
64	#include "tree-ssa-loop-niter.h"
65	#include "regs.h"
66	#include "function-abi.h"
67
68	/* Possible return values of iv_get_reaching_def. */
69
70	enum iv_grd_result
71	{
72	/* More than one reaching def, or reaching def that does not
73	dominate the use. */
74	GRD_INVALID,
75
76	/* The use is trivial invariant of the loop, i.e. is not changed
77	inside the loop. */
78	GRD_INVARIANT,
79
80	/* The use is reached by initial value and a value from the
81	previous iteration. */
82	GRD_MAYBE_BIV,
83
84	/* The use has single dominating def. */
85	GRD_SINGLE_DOM
86	};
87
88	/* Information about a biv. */
89
90	class biv_entry
91	{
92	public:
93	unsigned regno; /* The register of the biv. */
94	class rtx_iv iv; /* Value of the biv. */
95	};
96
97	static bool clean_slate = true;
98
99	static unsigned int iv_ref_table_size = 0;
100
101	/* Table of rtx_ivs indexed by the df_ref uid field. */
102	static class rtx_iv ** iv_ref_table;
103
104	/* Induction variable stored at the reference. */
105	#define DF_REF_IV(REF)iv_ref_table[((REF)->base.id)] iv_ref_table[DF_REF_ID (REF)((REF)->base.id)]
106	#define DF_REF_IV_SET(REF, IV)iv_ref_table[((REF)->base.id)] = (IV) iv_ref_table[DF_REF_ID (REF)((REF)->base.id)] = (IV)
107
108	/* The current loop. */
109
110	static class loop *current_loop;
111
112	/* Hashtable helper. */
113
114	struct biv_entry_hasher : free_ptr_hash <biv_entry>
115	{
116	typedef rtx_def *compare_type;
117	static inline hashval_t hash (const biv_entry *);
118	static inline bool equal (const biv_entry , const rtx_def );
119	};
120
121	/* Returns hash value for biv B. */
122
123	inline hashval_t
124	biv_entry_hasher::hash (const biv_entry *b)
125	{
126	return b->regno;
127	}
128
129	/* Compares biv B and register R. */
130
131	inline bool
132	biv_entry_hasher::equal (const biv_entry b, const rtx_def r)
133	{
134	return b->regno == REGNO (r)(rhs_regno(r));
135	}
136
137	/* Bivs of the current loop. */
138
139	static hash_table<biv_entry_hasher> *bivs;
140
141	static bool iv_analyze_op (rtx_insn , scalar_int_mode, rtx, class rtx_iv );
142
143	/* Return the RTX code corresponding to the IV extend code EXTEND. */
144	static inline enum rtx_code
145	iv_extend_to_rtx_code (enum iv_extend_code extend)
146	{
147	switch (extend)
148	{
149	case IV_SIGN_EXTEND:
150	return SIGN_EXTEND;
151	case IV_ZERO_EXTEND:
152	return ZERO_EXTEND;
153	case IV_UNKNOWN_EXTEND:
154	return UNKNOWN;
155	}
156	gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 156, __FUNCTION__));
157	}
158
159	/* Dumps information about IV to FILE. */
160
161	extern void dump_iv_info (FILE , class rtx_iv );
162	void
163	dump_iv_info (FILE file, class rtx_iv iv)
164	{
165	if (!iv->base)
166	{
167	fprintf (file, "not simple");
168	return;
169	}
170
171	if (iv->step == const0_rtx(const_int_rtx[64])
172	&& !iv->first_special)
173	fprintf (file, "invariant ");
174
175	print_rtl (file, iv->base);
176	if (iv->step != const0_rtx(const_int_rtx[64]))
177	{
178	fprintf (file, " + ");
179	print_rtl (file, iv->step);
180	fprintf (file, " * iteration");
181	}
182	fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode)mode_name[iv->mode]);
183
184	if (iv->mode != iv->extend_mode)
185	fprintf (file, " %s to %s",
186	rtx_name[iv_extend_to_rtx_code (iv->extend)],
187	GET_MODE_NAME (iv->extend_mode)mode_name[iv->extend_mode]);
188
189	if (iv->mult != const1_rtx(const_int_rtx[64 +1]))
190	{
191	fprintf (file, " * ");
192	print_rtl (file, iv->mult);
193	}
194	if (iv->delta != const0_rtx(const_int_rtx[64]))
195	{
196	fprintf (file, " + ");
197	print_rtl (file, iv->delta);
198	}
199	if (iv->first_special)
200	fprintf (file, " (first special)");
201	}
202
203	static void
204	check_iv_ref_table_size (void)
205	{
206	if (iv_ref_table_size < DF_DEFS_TABLE_SIZE ()(df->def_info.table_size))
207	{
208	unsigned int new_size = DF_DEFS_TABLE_SIZE ()(df->def_info.table_size) + (DF_DEFS_TABLE_SIZE ()(df->def_info.table_size) / 4);
209	iv_ref_table = XRESIZEVEC (class rtx_iv , iv_ref_table, new_size)((class rtx_iv ) xrealloc ((void ) (iv_ref_table), sizeof (class rtx_iv ) (new_size)));
210	memset (&iv_ref_table[iv_ref_table_size], 0,
211	(new_size - iv_ref_table_size) * sizeof (class rtx_iv *));
212	iv_ref_table_size = new_size;
213	}
214	}
215
216
217	/* Checks whether REG is a well-behaved register. */
218
219	static bool
220	simple_reg_p (rtx reg)
221	{
222	unsigned r;
223
224	if (GET_CODE (reg)((enum rtx_code) (reg)->code) == SUBREG)
225	{
226	if (!subreg_lowpart_p (reg))
227	return false;
228	reg = SUBREG_REG (reg)(((reg)->u.fld[0]).rt_rtx);
229	}
230
231	if (!REG_P (reg)(((enum rtx_code) (reg)->code) == REG))
232	return false;
233
234	r = REGNO (reg)(rhs_regno(reg));
235	if (HARD_REGISTER_NUM_P (r)((r) < 76))
236	return false;
237
238	if (GET_MODE_CLASS (GET_MODE (reg))((enum mode_class) mode_class[((machine_mode) (reg)->mode) ]) != MODE_INT)
239	return false;
240
241	return true;
242	}
243
244	/* Clears the information about ivs stored in df. */
245
246	static void
247	clear_iv_info (void)
248	{
249	unsigned i, n_defs = DF_DEFS_TABLE_SIZE ()(df->def_info.table_size);
250	class rtx_iv *iv;
251
252	check_iv_ref_table_size ();
253	for (i = 0; i < n_defs; i++)
254	{
255	iv = iv_ref_table[i];
256	if (iv)
257	{
258	free (iv);
259	iv_ref_table[i] = NULL__null;
260	}
261	}
262
263	bivs->empty ();
264	}
265
266
267	/* Prepare the data for an induction variable analysis of a LOOP. */
268
269	void
270	iv_analysis_loop_init (class loop *loop)
271	{
272	current_loop = loop;
273
274	/* Clear the information from the analysis of the previous loop. */
275	if (clean_slate)
276	{
277	df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
278	bivs = new hash_table<biv_entry_hasher> (10);
279	clean_slate = false;
280	}
281	else
282	clear_iv_info ();
283
284	/* Get rid of the ud chains before processing the rescans. Then add
285	the problem back. */
286	df_remove_problem (df_chain(df->problems_by_index[DF_CHAIN]));
287	df_process_deferred_rescans ();
288	df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
289	df_chain_add_problem (DF_UD_CHAIN);
290	df_note_add_problem ();
291	df_analyze_loop (loop);
292	if (dump_file)
293	df_dump_region (dump_file);
294
295	check_iv_ref_table_size ();
296	}
297
298	/* Finds the definition of REG that dominates loop latch and stores
299	it to DEF. Returns false if there is not a single definition
300	dominating the latch. If REG has no definition in loop, DEF
301	is set to NULL and true is returned. */
302
303	static bool
304	latch_dominating_def (rtx reg, df_ref *def)
305	{
306	df_ref single_rd = NULL__null, adef;
307	unsigned regno = REGNO (reg)(rhs_regno(reg));
308	class df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch)(df_rd_get_bb_info ((current_loop->latch)->index));
309
310	for (adef = DF_REG_DEF_CHAIN (regno)(df->def_regs[(regno)]->reg_chain); adef; adef = DF_REF_NEXT_REG (adef)((adef)->base.next_reg))
311	{
312	if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef)(((((adef)->base.cl) == DF_REF_ARTIFICIAL) ? (adef)->artificial_ref .bb : BLOCK_FOR_INSN (((adef)->base.insn_info->insn)))-> index))
313	\|\| !bitmap_bit_p (&bb_info->out, DF_REF_ID (adef)((adef)->base.id)))
314	continue;
315
316	/* More than one reaching definition. */
317	if (single_rd)
318	return false;
319
320	if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)((((adef)->base.cl) == DF_REF_ARTIFICIAL) ? (adef)->artificial_ref .bb : BLOCK_FOR_INSN (((adef)->base.insn_info->insn)))))
321	return false;
322
323	single_rd = adef;
324	}
325
326	*def = single_rd;
327	return true;
328	}
329
330	/* Gets definition of REG reaching its use in INSN and stores it to DEF. */
331
332	static enum iv_grd_result
333	iv_get_reaching_def (rtx_insn insn, rtx reg, df_ref def)
334	{
335	df_ref use, adef;
336	basic_block def_bb, use_bb;
337	rtx_insn *def_insn;
338	bool dom_p;
339
340	*def = NULL__null;
341	if (!simple_reg_p (reg))
342	return GRD_INVALID;
343	if (GET_CODE (reg)((enum rtx_code) (reg)->code) == SUBREG)
344	reg = SUBREG_REG (reg)(((reg)->u.fld[0]).rt_rtx);
345	gcc_assert (REG_P (reg))((void)(!((((enum rtx_code) (reg)->code) == REG)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 345, __FUNCTION__), 0 : 0));
346
347	use = df_find_use (insn, reg);
348	gcc_assert (use != NULL)((void)(!(use != __null) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 348, __FUNCTION__), 0 : 0));
349
350	if (!DF_REF_CHAIN (use)((use)->base.chain))
351	return GRD_INVARIANT;
352
353	/* More than one reaching def. */
354	if (DF_REF_CHAIN (use)((use)->base.chain)->next)
355	return GRD_INVALID;
356
357	adef = DF_REF_CHAIN (use)((use)->base.chain)->ref;
358
359	/* We do not handle setting only part of the register. */
360	if (DF_REF_FLAGS (adef)((adef)->base.flags) & DF_REF_READ_WRITE)
361	return GRD_INVALID;
362
363	def_insn = DF_REF_INSN (adef)((adef)->base.insn_info->insn);
364	def_bb = DF_REF_BB (adef)((((adef)->base.cl) == DF_REF_ARTIFICIAL) ? (adef)->artificial_ref .bb : BLOCK_FOR_INSN (((adef)->base.insn_info->insn)));
365	use_bb = BLOCK_FOR_INSN (insn);
366
367	if (use_bb == def_bb)
368	dom_p = (DF_INSN_LUID (def_insn)((((df->insns[(INSN_UID (def_insn))]))->luid)) < DF_INSN_LUID (insn)((((df->insns[(INSN_UID (insn))]))->luid)));
369	else
370	dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
371
372	if (dom_p)
373	{
374	*def = adef;
375	return GRD_SINGLE_DOM;
376	}
377
378	/* The definition does not dominate the use. This is still OK if
379	this may be a use of a biv, i.e. if the def_bb dominates loop
380	latch. */
381	if (just_once_each_iteration_p (current_loop, def_bb))
382	return GRD_MAYBE_BIV;
383
384	return GRD_INVALID;
385	}
386
387	/* Sets IV to invariant CST in MODE. Always returns true (just for
388	consistency with other iv manipulation functions that may fail). */
389
390	static bool
391	iv_constant (class rtx_iv *iv, scalar_int_mode mode, rtx cst)
392	{
393	iv->mode = mode;
394	iv->base = cst;
395	iv->step = const0_rtx(const_int_rtx[64]);
396	iv->first_special = false;
397	iv->extend = IV_UNKNOWN_EXTEND;
398	iv->extend_mode = iv->mode;
399	iv->delta = const0_rtx(const_int_rtx[64]);
400	iv->mult = const1_rtx(const_int_rtx[64 +1]);
401
402	return true;
403	}
404
405	/* Evaluates application of subreg to MODE on IV. */
406
407	static bool
408	iv_subreg (class rtx_iv *iv, scalar_int_mode mode)
409	{
410	/* If iv is invariant, just calculate the new value. */
411	if (iv->step == const0_rtx(const_int_rtx[64])
412	&& !iv->first_special)
413	{
414	rtx val = get_iv_value (iv, const0_rtx(const_int_rtx[64]));
415	val = lowpart_subreg (mode, val,
416	iv->extend == IV_UNKNOWN_EXTEND
417	? iv->mode : iv->extend_mode);
418
419	iv->base = val;
420	iv->extend = IV_UNKNOWN_EXTEND;
421	iv->mode = iv->extend_mode = mode;
422	iv->delta = const0_rtx(const_int_rtx[64]);
423	iv->mult = const1_rtx(const_int_rtx[64 +1]);
424	return true;
425	}
426
427	if (iv->extend_mode == mode)
428	return true;
429
430	if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
431	return false;
432
433	iv->extend = IV_UNKNOWN_EXTEND;
434	iv->mode = mode;
435
436	iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
437	simplify_gen_binary (MULT, iv->extend_mode,
438	iv->base, iv->mult));
439	iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
440	iv->mult = const1_rtx(const_int_rtx[64 +1]);
441	iv->delta = const0_rtx(const_int_rtx[64]);
442	iv->first_special = false;
443
444	return true;
445	}
446
447	/* Evaluates application of EXTEND to MODE on IV. */
448
449	static bool
450	iv_extend (class rtx_iv *iv, enum iv_extend_code extend, scalar_int_mode mode)
451	{
452	/* If iv is invariant, just calculate the new value. */
453	if (iv->step == const0_rtx(const_int_rtx[64])
454	&& !iv->first_special)
455	{
456	rtx val = get_iv_value (iv, const0_rtx(const_int_rtx[64]));
457	if (iv->extend_mode != iv->mode
458	&& iv->extend != IV_UNKNOWN_EXTEND
459	&& iv->extend != extend)
460	val = lowpart_subreg (iv->mode, val, iv->extend_mode);
461	val = simplify_gen_unary (iv_extend_to_rtx_code (extend), mode,
462	val,
463	iv->extend == extend
464	? iv->extend_mode : iv->mode);
465	iv->base = val;
466	iv->extend = IV_UNKNOWN_EXTEND;
467	iv->mode = iv->extend_mode = mode;
468	iv->delta = const0_rtx(const_int_rtx[64]);
469	iv->mult = const1_rtx(const_int_rtx[64 +1]);
470	return true;
471	}
472
473	if (mode != iv->extend_mode)
474	return false;
475
476	if (iv->extend != IV_UNKNOWN_EXTEND
477	&& iv->extend != extend)
478	return false;
479
480	iv->extend = extend;
481
482	return true;
483	}
484
485	/* Evaluates negation of IV. */
486
487	static bool
488	iv_neg (class rtx_iv *iv)
489	{
490	if (iv->extend == IV_UNKNOWN_EXTEND)
491	{
492	iv->base = simplify_gen_unary (NEG, iv->extend_mode,
493	iv->base, iv->extend_mode);
494	iv->step = simplify_gen_unary (NEG, iv->extend_mode,
495	iv->step, iv->extend_mode);
496	}
497	else
498	{
499	iv->delta = simplify_gen_unary (NEG, iv->extend_mode,
500	iv->delta, iv->extend_mode);
501	iv->mult = simplify_gen_unary (NEG, iv->extend_mode,
502	iv->mult, iv->extend_mode);
503	}
504
505	return true;
506	}
507
508	/* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
509
510	static bool
511	iv_add (class rtx_iv iv0, class rtx_iv iv1, enum rtx_code op)
512	{
513	scalar_int_mode mode;
514	rtx arg;
515
516	/* Extend the constant to extend_mode of the other operand if necessary. */
517	if (iv0->extend == IV_UNKNOWN_EXTEND
518	&& iv0->mode == iv0->extend_mode
519	&& iv0->step == const0_rtx(const_int_rtx[64])
520	&& GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
521	{
522	iv0->extend_mode = iv1->extend_mode;
523	iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
524	iv0->base, iv0->mode);
525	}
526	if (iv1->extend == IV_UNKNOWN_EXTEND
527	&& iv1->mode == iv1->extend_mode
528	&& iv1->step == const0_rtx(const_int_rtx[64])
529	&& GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
530	{
531	iv1->extend_mode = iv0->extend_mode;
532	iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
533	iv1->base, iv1->mode);
534	}
535
536	mode = iv0->extend_mode;
537	if (mode != iv1->extend_mode)
538	return false;
539
540	if (iv0->extend == IV_UNKNOWN_EXTEND
541	&& iv1->extend == IV_UNKNOWN_EXTEND)
542	{
543	if (iv0->mode != iv1->mode)
544	return false;
545
546	iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
547	iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);
548
549	return true;
550	}
551
552	/* Handle addition of constant. */
553	if (iv1->extend == IV_UNKNOWN_EXTEND
554	&& iv1->mode == mode
555	&& iv1->step == const0_rtx(const_int_rtx[64]))
556	{
557	iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base);
558	return true;
559	}
560
561	if (iv0->extend == IV_UNKNOWN_EXTEND
562	&& iv0->mode == mode
563	&& iv0->step == const0_rtx(const_int_rtx[64]))
564	{
565	arg = iv0->base;
566	iv0 = iv1;
567	if (op == MINUS
568	&& !iv_neg (iv0))
569	return false;
570
571	iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg);
572	return true;
573	}
574
575	return false;
576	}
577
578	/* Evaluates multiplication of IV by constant CST. */
579
580	static bool
581	iv_mult (class rtx_iv *iv, rtx mby)
582	{
583	scalar_int_mode mode = iv->extend_mode;
584
585	if (GET_MODE (mby)((machine_mode) (mby)->mode) != VOIDmode((void) 0, E_VOIDmode)
586	&& GET_MODE (mby)((machine_mode) (mby)->mode) != mode)
587	return false;
588
589	if (iv->extend == IV_UNKNOWN_EXTEND)
590	{
591	iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
592	iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
593	}
594	else
595	{
596	iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby);
597	iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby);
598	}
599
600	return true;
601	}
602
603	/* Evaluates shift of IV by constant CST. */
604
605	static bool
606	iv_shift (class rtx_iv *iv, rtx mby)
607	{
608	scalar_int_mode mode = iv->extend_mode;
609
610	if (GET_MODE (mby)((machine_mode) (mby)->mode) != VOIDmode((void) 0, E_VOIDmode)
611	&& GET_MODE (mby)((machine_mode) (mby)->mode) != mode)
612	return false;
613
614	if (iv->extend == IV_UNKNOWN_EXTEND)
615	{
616	iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
617	iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
618	}
619	else
620	{
621	iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
622	iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
623	}
624
625	return true;
626	}
627
628	/* The recursive part of get_biv_step. Gets the value of the single value
629	defined by DEF wrto initial value of REG inside loop, in shape described
630	at get_biv_step. */
631
632	static bool
633	get_biv_step_1 (df_ref def, scalar_int_mode outer_mode, rtx reg,
634	rtx inner_step, scalar_int_mode inner_mode,
635	enum iv_extend_code *extend,
636	rtx *outer_step)
637	{
638	rtx set, rhs, op0 = NULL_RTX(rtx) 0, op1 = NULL_RTX(rtx) 0;
639	rtx next, nextr;
640	enum rtx_code code;
641	rtx_insn *insn = DF_REF_INSN (def)((def)->base.insn_info->insn);
642	df_ref next_def;
643	enum iv_grd_result res;
644
645	set = single_set (insn);
646	if (!set)
647	return false;
648
649	rhs = find_reg_equal_equiv_note (insn);
650	if (rhs)
651	rhs = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
652	else
653	rhs = SET_SRC (set)(((set)->u.fld[1]).rt_rtx);
654
655	code = GET_CODE (rhs)((enum rtx_code) (rhs)->code);
656	switch (code)
657	{
658	case SUBREG:
659	case REG:
660	next = rhs;
661	break;
662
663	case PLUS:
664	case MINUS:
665	op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
666	op1 = XEXP (rhs, 1)(((rhs)->u.fld[1]).rt_rtx);
667
668	if (code == PLUS && CONSTANT_P (op0)((rtx_class[(int) (((enum rtx_code) (op0)->code))]) == RTX_CONST_OBJ ))
669	std::swap (op0, op1);
670
671	if (!simple_reg_p (op0)
672	\|\| !CONSTANT_P (op1)((rtx_class[(int) (((enum rtx_code) (op1)->code))]) == RTX_CONST_OBJ ))
673	return false;
674
675	if (GET_MODE (rhs)((machine_mode) (rhs)->mode) != outer_mode)
676	{
677	/* ppc64 uses expressions like
678
679	(set x:SI (plus:SI (subreg:SI y:DI) 1)).
680
681	this is equivalent to
682
683	(set x':DI (plus:DI y:DI 1))
684	(set x:SI (subreg:SI (x':DI)). */
685	if (GET_CODE (op0)((enum rtx_code) (op0)->code) != SUBREG)
686	return false;
687	if (GET_MODE (SUBREG_REG (op0))((machine_mode) ((((op0)->u.fld[0]).rt_rtx))->mode) != outer_mode)
688	return false;
689	}
690
691	next = op0;
692	break;
693
694	case SIGN_EXTEND:
695	case ZERO_EXTEND:
696	if (GET_MODE (rhs)((machine_mode) (rhs)->mode) != outer_mode)
697	return false;
698
699	op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
700	if (!simple_reg_p (op0))
701	return false;
702
703	next = op0;
704	break;
705
706	default:
707	return false;
708	}
709
710	if (GET_CODE (next)((enum rtx_code) (next)->code) == SUBREG)
711	{
712	if (!subreg_lowpart_p (next))
713	return false;
714
715	nextr = SUBREG_REG (next)(((next)->u.fld[0]).rt_rtx);
716	if (GET_MODE (nextr)((machine_mode) (nextr)->mode) != outer_mode)
717	return false;
718	}
719	else
720	nextr = next;
721
722	res = iv_get_reaching_def (insn, nextr, &next_def);
723
724	if (res == GRD_INVALID \|\| res == GRD_INVARIANT)
725	return false;
726
727	if (res == GRD_MAYBE_BIV)
728	{
729	if (!rtx_equal_p (nextr, reg))
730	return false;
731
732	*inner_step = const0_rtx(const_int_rtx[64]);
733	*extend = IV_UNKNOWN_EXTEND;
734	*inner_mode = outer_mode;
735	*outer_step = const0_rtx(const_int_rtx[64]);
736	}
737	else if (!get_biv_step_1 (next_def, outer_mode, reg,
738	inner_step, inner_mode, extend,
739	outer_step))
740	return false;
741
742	if (GET_CODE (next)((enum rtx_code) (next)->code) == SUBREG)
743	{
744	scalar_int_mode amode;
745	if (!is_a <scalar_int_mode> (GET_MODE (next)((machine_mode) (next)->mode), &amode)
746	\|\| GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
747	return false;
748
749	*inner_mode = amode;
750	*inner_step = simplify_gen_binary (PLUS, outer_mode,
751	inner_step, outer_step);
752	*outer_step = const0_rtx(const_int_rtx[64]);
753	*extend = IV_UNKNOWN_EXTEND;
754	}
755
756	switch (code)
757	{
758	case REG:
759	case SUBREG:
760	break;
761
762	case PLUS:
763	case MINUS:
764	if (*inner_mode == outer_mode
765	/* See comment in previous switch. */
766	\|\| GET_MODE (rhs)((machine_mode) (rhs)->mode) != outer_mode)
767	*inner_step = simplify_gen_binary (code, outer_mode,
768	*inner_step, op1);
769	else
770	*outer_step = simplify_gen_binary (code, outer_mode,
771	*outer_step, op1);
772	break;
773
774	case SIGN_EXTEND:
775	case ZERO_EXTEND:
776	gcc_assert (GET_MODE (op0) == inner_mode((void)(!(((machine_mode) (op0)->mode) == inner_mode && extend == IV_UNKNOWN_EXTEND && outer_step == (const_int_rtx [64])) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 778, __FUNCTION__), 0 : 0))
777	&& extend == IV_UNKNOWN_EXTEND((void)(!(((machine_mode) (op0)->mode) == inner_mode && extend == IV_UNKNOWN_EXTEND && outer_step == (const_int_rtx [64])) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 778, __FUNCTION__), 0 : 0))
778	&& outer_step == const0_rtx)((void)(!(((machine_mode) (op0)->mode) == inner_mode && extend == IV_UNKNOWN_EXTEND && outer_step == (const_int_rtx [64])) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 778, __FUNCTION__), 0 : 0));
779
780	*extend = (code == SIGN_EXTEND) ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
781	break;
782
783	default:
784	return false;
785	}
786
787	return true;
788	}
789
790	/* Gets the operation on register REG inside loop, in shape
791
792	OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
793
794	If the operation cannot be described in this shape, return false.
795	LAST_DEF is the definition of REG that dominates loop latch. */
796
797	static bool
798	get_biv_step (df_ref last_def, scalar_int_mode outer_mode, rtx reg,
799	rtx inner_step, scalar_int_mode inner_mode,
800	enum iv_extend_code extend, rtx outer_step)
801	{
802	if (!get_biv_step_1 (last_def, outer_mode, reg,
803	inner_step, inner_mode, extend,
804	outer_step))
805	return false;
806
807	gcc_assert ((inner_mode == outer_mode) != (extend != IV_UNKNOWN_EXTEND))((void)(!((inner_mode == outer_mode) != (extend != IV_UNKNOWN_EXTEND )) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 807, __FUNCTION__), 0 : 0));
808	gcc_assert (inner_mode != outer_mode \|\| outer_step == const0_rtx)((void)(!(inner_mode != outer_mode \|\| outer_step == (const_int_rtx [64])) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 808, __FUNCTION__), 0 : 0));
809
810	return true;
811	}
812
813	/* Records information that DEF is induction variable IV. */
814
815	static void
816	record_iv (df_ref def, class rtx_iv *iv)
817	{
818	class rtx_iv recorded_iv = XNEW (class rtx_iv)((class rtx_iv ) xmalloc (sizeof (class rtx_iv)));
819
820	recorded_iv = iv;
821	check_iv_ref_table_size ();
822	DF_REF_IV_SET (def, recorded_iv)iv_ref_table[((def)->base.id)] = (recorded_iv);
823	}
824
825	/* If DEF was already analyzed for bivness, store the description of the biv to
826	IV and return true. Otherwise return false. */
827
828	static bool
829	analyzed_for_bivness_p (rtx def, class rtx_iv *iv)
830	{
831	class biv_entry *biv = bivs->find_with_hash (def, REGNO (def)(rhs_regno(def)));
832
833	if (!biv)
834	return false;
835
836	*iv = biv->iv;
837	return true;
838	}
839
840	static void
841	record_biv (rtx def, class rtx_iv *iv)
842	{
843	class biv_entry biv = XNEW (class biv_entry)((class biv_entry ) xmalloc (sizeof (class biv_entry)));
844	biv_entry **slot = bivs->find_slot_with_hash (def, REGNO (def)(rhs_regno(def)), INSERT);
845
846	biv->regno = REGNO (def)(rhs_regno(def));
847	biv->iv = *iv;
848	gcc_assert (!slot)((void)(!(!slot) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 848, __FUNCTION__), 0 : 0));
849	*slot = biv;
850	}
851
852	/* Determines whether DEF is a biv and if so, stores its description
853	to IV. OUTER_MODE is the mode of DEF. /
854
855	static bool
856	iv_analyze_biv (scalar_int_mode outer_mode, rtx def, class rtx_iv *iv)
857	{
858	rtx inner_step, outer_step;
859	scalar_int_mode inner_mode;
860	enum iv_extend_code extend;
861	df_ref last_def;
862
863	if (dump_file)
864	{
865	fprintf (dump_file, "Analyzing ");
866	print_rtl (dump_file, def);
867	fprintf (dump_file, " for bivness.\n");
868	}
869
870	if (!REG_P (def)(((enum rtx_code) (def)->code) == REG))
871	{
872	if (!CONSTANT_P (def)((rtx_class[(int) (((enum rtx_code) (def)->code))]) == RTX_CONST_OBJ ))
873	return false;
874
875	return iv_constant (iv, outer_mode, def);
876	}
877
878	if (!latch_dominating_def (def, &last_def))
879	{
880	if (dump_file)
881	fprintf (dump_file, " not simple.\n");
882	return false;
883	}
884
885	if (!last_def)
886	return iv_constant (iv, outer_mode, def);
887
888	if (analyzed_for_bivness_p (def, iv))
889	{
890	if (dump_file)
891	fprintf (dump_file, " already analysed.\n");
892	return iv->base != NULL_RTX(rtx) 0;
893	}
894
895	if (!get_biv_step (last_def, outer_mode, def, &inner_step, &inner_mode,
896	&extend, &outer_step))
897	{
898	iv->base = NULL_RTX(rtx) 0;
899	goto end;
900	}
901
902	/* Loop transforms base to es (base + inner_step) + outer_step,
903	where es means extend of subreg between inner_mode and outer_mode.
904	The corresponding induction variable is
905
906	es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
907
908	iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step);
909	iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step);
910	iv->mode = inner_mode;
911	iv->extend_mode = outer_mode;
912	iv->extend = extend;
913	iv->mult = const1_rtx(const_int_rtx[64 +1]);
914	iv->delta = outer_step;
915	iv->first_special = inner_mode != outer_mode;
916
917	end:
918	if (dump_file)
919	{
920	fprintf (dump_file, " ");
921	dump_iv_info (dump_file, iv);
922	fprintf (dump_file, "\n");
923	}
924
925	record_biv (def, iv);
926	return iv->base != NULL_RTX(rtx) 0;
927	}
928
929	/* Analyzes expression RHS used at INSN and stores the result to *IV.
930	The mode of the induction variable is MODE. */
931
932	bool
933	iv_analyze_expr (rtx_insn *insn, scalar_int_mode mode, rtx rhs,
934	class rtx_iv *iv)
935	{
936	rtx mby = NULL_RTX(rtx) 0;
937	rtx op0 = NULL_RTX(rtx) 0, op1 = NULL_RTX(rtx) 0;
938	class rtx_iv iv0, iv1;
939	enum rtx_code code = GET_CODE (rhs)((enum rtx_code) (rhs)->code);
940	scalar_int_mode omode = mode;
941
942	iv->base = NULL_RTX(rtx) 0;
943	iv->step = NULL_RTX(rtx) 0;
944
945	gcc_assert (GET_MODE (rhs) == mode \|\| GET_MODE (rhs) == VOIDmode)((void)(!(((machine_mode) (rhs)->mode) == mode \|\| ((machine_mode ) (rhs)->mode) == ((void) 0, E_VOIDmode)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 945, __FUNCTION__), 0 : 0));
946
947	if (CONSTANT_P (rhs)((rtx_class[(int) (((enum rtx_code) (rhs)->code))]) == RTX_CONST_OBJ )
948	\|\| REG_P (rhs)(((enum rtx_code) (rhs)->code) == REG)
949	\|\| code == SUBREG)
950	return iv_analyze_op (insn, mode, rhs, iv);
951
952	switch (code)
953	{
954	case REG:
955	op0 = rhs;
956	break;
957
958	case SIGN_EXTEND:
959	case ZERO_EXTEND:
960	case NEG:
961	op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
962	/* We don't know how many bits there are in a sign-extended constant. */
963	if (!is_a <scalar_int_mode> (GET_MODE (op0)((machine_mode) (op0)->mode), &omode))
964	return false;
965	break;
966
967	case PLUS:
968	case MINUS:
969	op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
970	op1 = XEXP (rhs, 1)(((rhs)->u.fld[1]).rt_rtx);
971	break;
972
973	case MULT:
974	op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
975	mby = XEXP (rhs, 1)(((rhs)->u.fld[1]).rt_rtx);
976	if (!CONSTANT_P (mby)((rtx_class[(int) (((enum rtx_code) (mby)->code))]) == RTX_CONST_OBJ ))
977	std::swap (op0, mby);
978	if (!CONSTANT_P (mby)((rtx_class[(int) (((enum rtx_code) (mby)->code))]) == RTX_CONST_OBJ ))
979	return false;
980	break;
981
982	case ASHIFT:
983	op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
984	mby = XEXP (rhs, 1)(((rhs)->u.fld[1]).rt_rtx);
985	if (!CONSTANT_P (mby)((rtx_class[(int) (((enum rtx_code) (mby)->code))]) == RTX_CONST_OBJ ))
986	return false;
987	break;
988
989	default:
990	return false;
991	}
992
993	if (op0
994	&& !iv_analyze_expr (insn, omode, op0, &iv0))
995	return false;
996
997	if (op1
998	&& !iv_analyze_expr (insn, omode, op1, &iv1))
999	return false;
1000
1001	switch (code)
1002	{
1003	case SIGN_EXTEND:
1004	if (!iv_extend (&iv0, IV_SIGN_EXTEND, mode))
1005	return false;
1006	break;
1007
1008	case ZERO_EXTEND:
1009	if (!iv_extend (&iv0, IV_ZERO_EXTEND, mode))
1010	return false;
1011	break;
1012
1013	case NEG:
1014	if (!iv_neg (&iv0))
1015	return false;
1016	break;
1017
1018	case PLUS:
1019	case MINUS:
1020	if (!iv_add (&iv0, &iv1, code))
1021	return false;
1022	break;
1023
1024	case MULT:
1025	if (!iv_mult (&iv0, mby))
1026	return false;
1027	break;
1028
1029	case ASHIFT:
1030	if (!iv_shift (&iv0, mby))
1031	return false;
1032	break;
1033
1034	default:
1035	break;
1036	}
1037
1038	*iv = iv0;
1039	return iv->base != NULL_RTX(rtx) 0;
1040	}
1041
1042	/* Analyzes iv DEF and stores the result to IV. /
1043
1044	static bool
1045	iv_analyze_def (df_ref def, class rtx_iv *iv)
1046	{
1047	rtx_insn *insn = DF_REF_INSN (def)((def)->base.insn_info->insn);
1048	rtx reg = DF_REF_REG (def)((def)->base.reg);
1049	rtx set, rhs;
1050
1051	if (dump_file)
1052	{
1053	fprintf (dump_file, "Analyzing def of ");
1054	print_rtl (dump_file, reg);
1055	fprintf (dump_file, " in insn ");
1056	print_rtl_single (dump_file, insn);
1057	}
1058
1059	check_iv_ref_table_size ();
1060	if (DF_REF_IV (def)iv_ref_table[((def)->base.id)])
1061	{
1062	if (dump_file)
1063	fprintf (dump_file, " already analysed.\n");
1064	iv = DF_REF_IV (def)iv_ref_table[((def)->base.id)];
1065	return iv->base != NULL_RTX(rtx) 0;
1066	}
1067
1068	iv->base = NULL_RTX(rtx) 0;
1069	iv->step = NULL_RTX(rtx) 0;
1070
1071	scalar_int_mode mode;
1072	if (!REG_P (reg)(((enum rtx_code) (reg)->code) == REG) \|\| !is_a <scalar_int_mode> (GET_MODE (reg)((machine_mode) (reg)->mode), &mode))
1073	return false;
1074
1075	set = single_set (insn);
1076	if (!set)
1077	return false;
1078
1079	if (!REG_P (SET_DEST (set))(((enum rtx_code) ((((set)->u.fld[0]).rt_rtx))->code) == REG))
1080	return false;
1081
1082	gcc_assert (SET_DEST (set) == reg)((void)(!((((set)->u.fld[0]).rt_rtx) == reg) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 1082, __FUNCTION__), 0 : 0));
1083	rhs = find_reg_equal_equiv_note (insn);
1084	if (rhs)
1085	rhs = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
1086	else
1087	rhs = SET_SRC (set)(((set)->u.fld[1]).rt_rtx);
1088
1089	iv_analyze_expr (insn, mode, rhs, iv);
1090	record_iv (def, iv);
1091
1092	if (dump_file)
1093	{
1094	print_rtl (dump_file, reg);
1095	fprintf (dump_file, " in insn ");
1096	print_rtl_single (dump_file, insn);
1097	fprintf (dump_file, " is ");
1098	dump_iv_info (dump_file, iv);
1099	fprintf (dump_file, "\n");
1100	}
1101
1102	return iv->base != NULL_RTX(rtx) 0;
1103	}
1104
1105	/* Analyzes operand OP of INSN and stores the result to *IV. MODE is the
1106	mode of OP. */
1107
1108	static bool
1109	iv_analyze_op (rtx_insn insn, scalar_int_mode mode, rtx op, class rtx_iv iv)
1110	{
1111	df_ref def = NULL__null;
1112	enum iv_grd_result res;
1113
1114	if (dump_file)
1115	{
1116	fprintf (dump_file, "Analyzing operand ");
1117	print_rtl (dump_file, op);
1118	fprintf (dump_file, " of insn ");
1119	print_rtl_single (dump_file, insn);
1120	}
1121
1122	if (function_invariant_p (op))
1123	res = GRD_INVARIANT;
1124	else if (GET_CODE (op)((enum rtx_code) (op)->code) == SUBREG)
1125	{
1126	scalar_int_mode inner_mode;
1127	if (!subreg_lowpart_p (op)
1128	\|\| !is_a <scalar_int_mode> (GET_MODE (SUBREG_REG (op))((machine_mode) ((((op)->u.fld[0]).rt_rtx))->mode), &inner_mode))
1129	return false;
1130
1131	if (!iv_analyze_op (insn, inner_mode, SUBREG_REG (op)(((op)->u.fld[0]).rt_rtx), iv))
1132	return false;
1133
1134	return iv_subreg (iv, mode);
1135	}
1136	else
1137	{
1138	res = iv_get_reaching_def (insn, op, &def);
1139	if (res == GRD_INVALID)
1140	{
1141	if (dump_file)
1142	fprintf (dump_file, " not simple.\n");
1143	return false;
1144	}
1145	}
1146
1147	if (res == GRD_INVARIANT)
1148	{
1149	iv_constant (iv, mode, op);
1150
1151	if (dump_file)
1152	{
1153	fprintf (dump_file, " ");
1154	dump_iv_info (dump_file, iv);
1155	fprintf (dump_file, "\n");
1156	}
1157	return true;
1158	}
1159
1160	if (res == GRD_MAYBE_BIV)
1161	return iv_analyze_biv (mode, op, iv);
1162
1163	return iv_analyze_def (def, iv);
1164	}
1165
1166	/* Analyzes value VAL at INSN and stores the result to *IV. MODE is the
1167	mode of VAL. */
1168
1169	bool
1170	iv_analyze (rtx_insn insn, scalar_int_mode mode, rtx val, class rtx_iv iv)
1171	{
1172	rtx reg;
1173
1174	/* We must find the insn in that val is used, so that we get to UD chains.
1175	Since the function is sometimes called on result of get_condition,
1176	this does not necessarily have to be directly INSN; scan also the
1177	following insns. */
1178	if (simple_reg_p (val))
1179	{
1180	if (GET_CODE (val)((enum rtx_code) (val)->code) == SUBREG)
1181	reg = SUBREG_REG (val)(((val)->u.fld[0]).rt_rtx);
1182	else
1183	reg = val;
1184
1185	while (!df_find_use (insn, reg))
1186	insn = NEXT_INSN (insn);
1187	}
1188
1189	return iv_analyze_op (insn, mode, val, iv);
1190	}
1191
1192	/* Analyzes definition of DEF in INSN and stores the result to IV. */
1193
1194	bool
1195	iv_analyze_result (rtx_insn insn, rtx def, class rtx_iv iv)
1196	{
1197	df_ref adef;
1198
1199	adef = df_find_def (insn, def);
1200	if (!adef)
1201	return false;
1202
1203	return iv_analyze_def (adef, iv);
1204	}
1205
1206	/* Checks whether definition of register REG in INSN is a basic induction
1207	variable. MODE is the mode of REG.
1208
1209	IV analysis must have been initialized (via a call to
1210	iv_analysis_loop_init) for this function to produce a result. */
1211
1212	bool
1213	biv_p (rtx_insn *insn, scalar_int_mode mode, rtx reg)
1214	{
1215	class rtx_iv iv;
1216	df_ref def, last_def;
1217
1218	if (!simple_reg_p (reg))
1219	return false;
1220
1221	def = df_find_def (insn, reg);
1222	gcc_assert (def != NULL)((void)(!(def != __null) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 1222, __FUNCTION__), 0 : 0));
1223	if (!latch_dominating_def (reg, &last_def))
1224	return false;
1225	if (last_def != def)
1226	return false;
1227
1228	if (!iv_analyze_biv (mode, reg, &iv))
1229	return false;
1230
1231	return iv.step != const0_rtx(const_int_rtx[64]);
1232	}
1233
1234	/* Calculates value of IV at ITERATION-th iteration. */
1235
1236	rtx
1237	get_iv_value (class rtx_iv *iv, rtx iteration)
1238	{
1239	rtx val;
1240
1241	/* We would need to generate some if_then_else patterns, and so far
1242	it is not needed anywhere. */
1243	gcc_assert (!iv->first_special)((void)(!(!iv->first_special) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 1243, __FUNCTION__), 0 : 0));
1244
1245	if (iv->step != const0_rtx(const_int_rtx[64]) && iteration != const0_rtx(const_int_rtx[64]))
1246	val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
1247	simplify_gen_binary (MULT, iv->extend_mode,
1248	iv->step, iteration));
1249	else
1250	val = iv->base;
1251
1252	if (iv->extend_mode == iv->mode)
1253	return val;
1254
1255	val = lowpart_subreg (iv->mode, val, iv->extend_mode);
1256
1257	if (iv->extend == IV_UNKNOWN_EXTEND)
1258	return val;
1259
1260	val = simplify_gen_unary (iv_extend_to_rtx_code (iv->extend),
1261	iv->extend_mode, val, iv->mode);
1262	val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
1263	simplify_gen_binary (MULT, iv->extend_mode,
1264	iv->mult, val));
1265
1266	return val;
1267	}
1268
1269	/* Free the data for an induction variable analysis. */
1270
1271	void
1272	iv_analysis_done (void)
1273	{
1274	if (!clean_slate)
1275	{
1276	clear_iv_info ();
1277	clean_slate = true;
1278	df_finish_pass (true);
1279	delete bivs;
1280	bivs = NULL__null;
1281	free (iv_ref_table);
1282	iv_ref_table = NULL__null;
1283	iv_ref_table_size = 0;
1284	}
1285	}
1286
1287	/* Computes inverse to X modulo (1 << MOD). */
1288
1289	static uint64_t
1290	inverse (uint64_t x, int mod)
1291	{
1292	uint64_t mask =
1293	((uint64_t) 1 << (mod - 1) << 1) - 1;
1294	uint64_t rslt = 1;
1295	int i;
1296
1297	for (i = 0; i < mod - 1; i++)
1298	{
1299	rslt = (rslt * x) & mask;
1300	x = (x * x) & mask;
1301	}
1302
1303	return rslt;
1304	}
1305
1306	/* Checks whether any register in X is in set ALT. */
1307
1308	static bool
1309	altered_reg_used (const_rtx x, bitmap alt)
1310	{
1311	subrtx_iterator::array_type array;
1312	FOR_EACH_SUBRTX (iter, array, x, NONCONST)for (subrtx_iterator iter (array, x, rtx_nonconst_subrtx_bounds ); !iter.at_end (); iter.next ())
1313	{
1314	const_rtx x = *iter;
1315	if (REG_P (x)(((enum rtx_code) (x)->code) == REG) && REGNO_REG_SET_P (alt, REGNO (x))bitmap_bit_p (alt, (rhs_regno(x))))
1316	return true;
1317	}
1318	return false;
1319	}
1320
1321	/* Marks registers altered by EXPR in set ALT. */
1322
1323	static void
1324	mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED__attribute__ ((__unused__)), void *alt)
1325	{
1326	if (GET_CODE (expr)((enum rtx_code) (expr)->code) == SUBREG)
1327	expr = SUBREG_REG (expr)(((expr)->u.fld[0]).rt_rtx);
1328	if (!REG_P (expr)(((enum rtx_code) (expr)->code) == REG))
1329	return;
1330
1331	SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr))bitmap_set_bit ((bitmap) alt, (rhs_regno(expr)));
1332	}
1333
1334	/* Checks whether RHS is simple enough to process. */
1335
1336	static bool
1337	simple_rhs_p (rtx rhs)
1338	{
1339	rtx op0, op1;
1340
1341	if (function_invariant_p (rhs)
1342	\|\| (REG_P (rhs)(((enum rtx_code) (rhs)->code) == REG) && !HARD_REGISTER_P (rhs)((((rhs_regno(rhs))) < 76))))
1343	return true;
1344
1345	switch (GET_CODE (rhs)((enum rtx_code) (rhs)->code))
1346	{
1347	case PLUS:
1348	case MINUS:
1349	case AND:
1350	op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
1351	op1 = XEXP (rhs, 1)(((rhs)->u.fld[1]).rt_rtx);
1352	/* Allow reg OP const and reg OP reg. */
1353	if (!(REG_P (op0)(((enum rtx_code) (op0)->code) == REG) && !HARD_REGISTER_P (op0)((((rhs_regno(op0))) < 76)))
1354	&& !function_invariant_p (op0))
1355	return false;
1356	if (!(REG_P (op1)(((enum rtx_code) (op1)->code) == REG) && !HARD_REGISTER_P (op1)((((rhs_regno(op1))) < 76)))
1357	&& !function_invariant_p (op1))
1358	return false;
1359
1360	return true;
1361
1362	case ASHIFT:
1363	case ASHIFTRT:
1364	case LSHIFTRT:
1365	case MULT:
1366	op0 = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
1367	op1 = XEXP (rhs, 1)(((rhs)->u.fld[1]).rt_rtx);
1368	/* Allow reg OP const. */
1369	if (!(REG_P (op0)(((enum rtx_code) (op0)->code) == REG) && !HARD_REGISTER_P (op0)((((rhs_regno(op0))) < 76))))
1370	return false;
1371	if (!function_invariant_p (op1))
1372	return false;
1373
1374	return true;
1375
1376	default:
1377	return false;
1378	}
1379	}
1380
1381	/* If REGNO has a single definition, return its known value, otherwise return
1382	null. */
1383
1384	static rtx
1385	find_single_def_src (unsigned int regno)
1386	{
1387	rtx src = NULL_RTX(rtx) 0;
1388
1389	/* Don't look through unbounded number of single definition REG copies,
1390	there might be loops for sources with uninitialized variables. */
1391	for (int cnt = 0; cnt < 128; cnt++)
1392	{
1393	df_ref adef = DF_REG_DEF_CHAIN (regno)(df->def_regs[(regno)]->reg_chain);
1394	if (adef == NULL__null \|\| DF_REF_NEXT_REG (adef)((adef)->base.next_reg) != NULL__null
1395	\|\| DF_REF_IS_ARTIFICIAL (adef)(((adef)->base.cl) == DF_REF_ARTIFICIAL))
1396	return NULL_RTX(rtx) 0;
1397
1398	rtx set = single_set (DF_REF_INSN (adef)((adef)->base.insn_info->insn));
1399	if (set == NULL__null \|\| !REG_P (SET_DEST (set))(((enum rtx_code) ((((set)->u.fld[0]).rt_rtx))->code) == REG)
1400	\|\| REGNO (SET_DEST (set))(rhs_regno((((set)->u.fld[0]).rt_rtx))) != regno)
1401	return NULL_RTX(rtx) 0;
1402
1403	rtx note = find_reg_equal_equiv_note (DF_REF_INSN (adef)((adef)->base.insn_info->insn));
1404	if (note && function_invariant_p (XEXP (note, 0)(((note)->u.fld[0]).rt_rtx)))
1405	{
1406	src = XEXP (note, 0)(((note)->u.fld[0]).rt_rtx);
1407	break;
1408	}
1409	src = SET_SRC (set)(((set)->u.fld[1]).rt_rtx);
1410
1411	if (REG_P (src)(((enum rtx_code) (src)->code) == REG))
1412	{
1413	regno = REGNO (src)(rhs_regno(src));
1414	continue;
1415	}
1416	break;
1417	}
1418	if (!function_invariant_p (src))
1419	return NULL_RTX(rtx) 0;
1420
1421	return src;
1422	}
1423
1424	/* If any registers in *EXPR that have a single definition, try to replace
1425	them with the known-equivalent values. */
1426
1427	static void
1428	replace_single_def_regs (rtx *expr)
1429	{
1430	subrtx_var_iterator::array_type array;
1431	repeat:
1432	FOR_EACH_SUBRTX_VAR (iter, array, expr, NONCONST)for (subrtx_var_iterator iter (array, expr, rtx_nonconst_subrtx_bounds ); !iter.at_end (); iter.next ())
1433	{
1434	rtx x = *iter;
1435	if (REG_P (x)(((enum rtx_code) (x)->code) == REG))
1436	if (rtx new_x = find_single_def_src (REGNO (x)(rhs_regno(x))))
1437	{
1438	expr = simplify_replace_rtx (expr, x, new_x);
1439	goto repeat;
1440	}
1441	}
1442	}
1443
1444	/* A subroutine of simplify_using_initial_values, this function examines INSN
1445	to see if it contains a suitable set that we can use to make a replacement.
1446	If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1447	the set; return false otherwise. */
1448
1449	static bool
1450	suitable_set_for_replacement (rtx_insn insn, rtx dest, rtx *src)
1451	{
1452	rtx set = single_set (insn);
1453	rtx lhs = NULL_RTX(rtx) 0, rhs;
1454
1455	if (!set)
1456	return false;
1457
1458	lhs = SET_DEST (set)(((set)->u.fld[0]).rt_rtx);
1459	if (!REG_P (lhs)(((enum rtx_code) (lhs)->code) == REG))
1460	return false;
1461
1462	rhs = find_reg_equal_equiv_note (insn);
1463	if (rhs)
1464	rhs = XEXP (rhs, 0)(((rhs)->u.fld[0]).rt_rtx);
1465	else
1466	rhs = SET_SRC (set)(((set)->u.fld[1]).rt_rtx);
1467
1468	if (!simple_rhs_p (rhs))
1469	return false;
1470
1471	*dest = lhs;
1472	*src = rhs;
1473	return true;
1474	}
1475
1476	/* Using the data returned by suitable_set_for_replacement, replace DEST
1477	with SRC in *EXPR and return the new expression. Also call
1478	replace_single_def_regs if the replacement changed something. */
1479	static void
1480	replace_in_expr (rtx *expr, rtx dest, rtx src)
1481	{
1482	rtx old = *expr;
1483	expr = simplify_replace_rtx (expr, dest, src);
1484	if (old == *expr)
1485	return;
1486	replace_single_def_regs (expr);
1487	}
1488
1489	/* Checks whether A implies B. */
1490
1491	static bool
1492	implies_p (rtx a, rtx b)
1493	{
1494	rtx op0, op1, opb0, opb1;
1495	machine_mode mode;
1496
1497	if (rtx_equal_p (a, b))
1498	return true;
1499
1500	if (GET_CODE (a)((enum rtx_code) (a)->code) == EQ)
1501	{
1502	op0 = XEXP (a, 0)(((a)->u.fld[0]).rt_rtx);
1503	op1 = XEXP (a, 1)(((a)->u.fld[1]).rt_rtx);
1504
1505	if (REG_P (op0)(((enum rtx_code) (op0)->code) == REG)
1506	\|\| (GET_CODE (op0)((enum rtx_code) (op0)->code) == SUBREG
1507	&& REG_P (SUBREG_REG (op0))(((enum rtx_code) ((((op0)->u.fld[0]).rt_rtx))->code) == REG)))
1508	{
1509	rtx r = simplify_replace_rtx (b, op0, op1);
1510	if (r == const_true_rtx)
1511	return true;
1512	}
1513
1514	if (REG_P (op1)(((enum rtx_code) (op1)->code) == REG)
1515	\|\| (GET_CODE (op1)((enum rtx_code) (op1)->code) == SUBREG
1516	&& REG_P (SUBREG_REG (op1))(((enum rtx_code) ((((op1)->u.fld[0]).rt_rtx))->code) == REG)))
1517	{
1518	rtx r = simplify_replace_rtx (b, op1, op0);
1519	if (r == const_true_rtx)
1520	return true;
1521	}
1522	}
1523
1524	if (b == const_true_rtx)
1525	return true;
1526
1527	if ((GET_RTX_CLASS (GET_CODE (a))(rtx_class[(int) (((enum rtx_code) (a)->code))]) != RTX_COMM_COMPARE
1528	&& GET_RTX_CLASS (GET_CODE (a))(rtx_class[(int) (((enum rtx_code) (a)->code))]) != RTX_COMPARE)
1529	\|\| (GET_RTX_CLASS (GET_CODE (b))(rtx_class[(int) (((enum rtx_code) (b)->code))]) != RTX_COMM_COMPARE
1530	&& GET_RTX_CLASS (GET_CODE (b))(rtx_class[(int) (((enum rtx_code) (b)->code))]) != RTX_COMPARE))
1531	return false;
1532
1533	op0 = XEXP (a, 0)(((a)->u.fld[0]).rt_rtx);
1534	op1 = XEXP (a, 1)(((a)->u.fld[1]).rt_rtx);
1535	opb0 = XEXP (b, 0)(((b)->u.fld[0]).rt_rtx);
1536	opb1 = XEXP (b, 1)(((b)->u.fld[1]).rt_rtx);
1537
1538	mode = GET_MODE (op0)((machine_mode) (op0)->mode);
1539	if (mode != GET_MODE (opb0)((machine_mode) (opb0)->mode))
1540	mode = VOIDmode((void) 0, E_VOIDmode);
1541	else if (mode == VOIDmode((void) 0, E_VOIDmode))
1542	{
1543	mode = GET_MODE (op1)((machine_mode) (op1)->mode);
1544	if (mode != GET_MODE (opb1)((machine_mode) (opb1)->mode))
1545	mode = VOIDmode((void) 0, E_VOIDmode);
1546	}
1547
1548	/* A < B implies A + 1 <= B. */
1549	if ((GET_CODE (a)((enum rtx_code) (a)->code) == GT \|\| GET_CODE (a)((enum rtx_code) (a)->code) == LT)
1550	&& (GET_CODE (b)((enum rtx_code) (b)->code) == GE \|\| GET_CODE (b)((enum rtx_code) (b)->code) == LE))
1551	{
1552
1553	if (GET_CODE (a)((enum rtx_code) (a)->code) == GT)
1554	std::swap (op0, op1);
1555
1556	if (GET_CODE (b)((enum rtx_code) (b)->code) == GE)
1557	std::swap (opb0, opb1);
1558
1559	if (SCALAR_INT_MODE_P (mode)(((enum mode_class) mode_class[mode]) == MODE_INT \|\| ((enum mode_class ) mode_class[mode]) == MODE_PARTIAL_INT)
1560	&& rtx_equal_p (op1, opb1)
1561	&& simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx(const_int_rtx[64 +1]))
1562	return true;
1563	return false;
1564	}
1565
1566	/* A < B or A > B imply A != B. TODO: Likewise
1567	A + n < B implies A != B + n if neither wraps. */
1568	if (GET_CODE (b)((enum rtx_code) (b)->code) == NE
1569	&& (GET_CODE (a)((enum rtx_code) (a)->code) == GT \|\| GET_CODE (a)((enum rtx_code) (a)->code) == GTU
1570	\|\| GET_CODE (a)((enum rtx_code) (a)->code) == LT \|\| GET_CODE (a)((enum rtx_code) (a)->code) == LTU))
1571	{
1572	if (rtx_equal_p (op0, opb0)
1573	&& rtx_equal_p (op1, opb1))
1574	return true;
1575	}
1576
1577	/* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
1578	if (GET_CODE (a)((enum rtx_code) (a)->code) == NE
1579	&& op1 == const0_rtx(const_int_rtx[64]))
1580	{
1581	if ((GET_CODE (b)((enum rtx_code) (b)->code) == GTU
1582	&& opb1 == const0_rtx(const_int_rtx[64]))
1583	\|\| (GET_CODE (b)((enum rtx_code) (b)->code) == GEU
1584	&& opb1 == const1_rtx(const_int_rtx[64 +1])))
1585	return rtx_equal_p (op0, opb0);
1586	}
1587
1588	/* A != N is equivalent to A - (N + 1) <u -1. */
1589	if (GET_CODE (a)((enum rtx_code) (a)->code) == NE
1590	&& CONST_INT_P (op1)(((enum rtx_code) (op1)->code) == CONST_INT)
1591	&& GET_CODE (b)((enum rtx_code) (b)->code) == LTU
1592	&& opb1 == constm1_rtx(const_int_rtx[64 -1])
1593	&& GET_CODE (opb0)((enum rtx_code) (opb0)->code) == PLUS
1594	&& CONST_INT_P (XEXP (opb0, 1))(((enum rtx_code) ((((opb0)->u.fld[1]).rt_rtx))->code) == CONST_INT)
1595	/* Avoid overflows. */
1596	&& ((unsigned HOST_WIDE_INTlong) INTVAL (XEXP (opb0, 1))(((((opb0)->u.fld[1]).rt_rtx))->u.hwint[0])
1597	!= ((unsigned HOST_WIDE_INTlong)1
1598	<< (HOST_BITS_PER_WIDE_INT64 - 1)) - 1)
1599	&& INTVAL (XEXP (opb0, 1))(((((opb0)->u.fld[1]).rt_rtx))->u.hwint[0]) + 1 == -INTVAL (op1)((op1)->u.hwint[0]))
1600	return rtx_equal_p (op0, XEXP (opb0, 0)(((opb0)->u.fld[0]).rt_rtx));
1601
1602	/* Likewise, A != N implies A - N > 0. */
1603	if (GET_CODE (a)((enum rtx_code) (a)->code) == NE
1604	&& CONST_INT_P (op1)(((enum rtx_code) (op1)->code) == CONST_INT))
1605	{
1606	if (GET_CODE (b)((enum rtx_code) (b)->code) == GTU
1607	&& GET_CODE (opb0)((enum rtx_code) (opb0)->code) == PLUS
1608	&& opb1 == const0_rtx(const_int_rtx[64])
1609	&& CONST_INT_P (XEXP (opb0, 1))(((enum rtx_code) ((((opb0)->u.fld[1]).rt_rtx))->code) == CONST_INT)
1610	/* Avoid overflows. */
1611	&& ((unsigned HOST_WIDE_INTlong) INTVAL (XEXP (opb0, 1))(((((opb0)->u.fld[1]).rt_rtx))->u.hwint[0])
1612	!= (HOST_WIDE_INT_1U1UL << (HOST_BITS_PER_WIDE_INT64 - 1)))
1613	&& rtx_equal_p (XEXP (opb0, 0)(((opb0)->u.fld[0]).rt_rtx), op0))
1614	return INTVAL (op1)((op1)->u.hwint[0]) == -INTVAL (XEXP (opb0, 1))(((((opb0)->u.fld[1]).rt_rtx))->u.hwint[0]);
1615	if (GET_CODE (b)((enum rtx_code) (b)->code) == GEU
1616	&& GET_CODE (opb0)((enum rtx_code) (opb0)->code) == PLUS
1617	&& opb1 == const1_rtx(const_int_rtx[64 +1])
1618	&& CONST_INT_P (XEXP (opb0, 1))(((enum rtx_code) ((((opb0)->u.fld[1]).rt_rtx))->code) == CONST_INT)
1619	/* Avoid overflows. */
1620	&& ((unsigned HOST_WIDE_INTlong) INTVAL (XEXP (opb0, 1))(((((opb0)->u.fld[1]).rt_rtx))->u.hwint[0])
1621	!= (HOST_WIDE_INT_1U1UL << (HOST_BITS_PER_WIDE_INT64 - 1)))
1622	&& rtx_equal_p (XEXP (opb0, 0)(((opb0)->u.fld[0]).rt_rtx), op0))
1623	return INTVAL (op1)((op1)->u.hwint[0]) == -INTVAL (XEXP (opb0, 1))(((((opb0)->u.fld[1]).rt_rtx))->u.hwint[0]);
1624	}
1625
1626	/* A >s X, where X is positive, implies A <u Y, if Y is negative. */
1627	if ((GET_CODE (a)((enum rtx_code) (a)->code) == GT \|\| GET_CODE (a)((enum rtx_code) (a)->code) == GE)
1628	&& CONST_INT_P (op1)(((enum rtx_code) (op1)->code) == CONST_INT)
1629	&& ((GET_CODE (a)((enum rtx_code) (a)->code) == GT && op1 == constm1_rtx(const_int_rtx[64 -1]))
1630	\|\| INTVAL (op1)((op1)->u.hwint[0]) >= 0)
1631	&& GET_CODE (b)((enum rtx_code) (b)->code) == LTU
1632	&& CONST_INT_P (opb1)(((enum rtx_code) (opb1)->code) == CONST_INT)
1633	&& rtx_equal_p (op0, opb0))
1634	return INTVAL (opb1)((opb1)->u.hwint[0]) < 0;
1635
1636	return false;
1637	}
1638
1639	/* Canonicalizes COND so that
1640
1641	(1) Ensure that operands are ordered according to
1642	swap_commutative_operands_p.
1643	(2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1644	for GE, GEU, and LEU. */
1645
1646	rtx
1647	canon_condition (rtx cond)
1648	{
1649	rtx op0, op1;
1650	enum rtx_code code;
1651	machine_mode mode;
1652
1653	code = GET_CODE (cond)((enum rtx_code) (cond)->code);
1654	op0 = XEXP (cond, 0)(((cond)->u.fld[0]).rt_rtx);
1655	op1 = XEXP (cond, 1)(((cond)->u.fld[1]).rt_rtx);
1656
1657	if (swap_commutative_operands_p (op0, op1))
1658	{
1659	code = swap_condition (code);
1660	std::swap (op0, op1);
1661	}
1662
1663	mode = GET_MODE (op0)((machine_mode) (op0)->mode);
1664	if (mode == VOIDmode((void) 0, E_VOIDmode))
1665	mode = GET_MODE (op1)((machine_mode) (op1)->mode);
1666	gcc_assert (mode != VOIDmode)((void)(!(mode != ((void) 0, E_VOIDmode)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 1666, __FUNCTION__), 0 : 0));
1667
1668	if (CONST_SCALAR_INT_P (op1)((((enum rtx_code) (op1)->code) == CONST_INT) \|\| (((enum rtx_code ) (op1)->code) == CONST_WIDE_INT)) && GET_MODE_CLASS (mode)((enum mode_class) mode_class[mode]) != MODE_CC)
1669	{
1670	rtx_mode_t const_val (op1, mode);
1671
1672	switch (code)
1673	{
1674	case LE:
1675	if (wi::ne_p (const_val, wi::max_value (mode, SIGNED)))
1676	{
1677	code = LT;
1678	op1 = immed_wide_int_const (wi::add (const_val, 1), mode);
1679	}
1680	break;
1681
1682	case GE:
1683	if (wi::ne_p (const_val, wi::min_value (mode, SIGNED)))
1684	{
1685	code = GT;
1686	op1 = immed_wide_int_const (wi::sub (const_val, 1), mode);
1687	}
1688	break;
1689
1690	case LEU:
1691	if (wi::ne_p (const_val, -1))
1692	{
1693	code = LTU;
1694	op1 = immed_wide_int_const (wi::add (const_val, 1), mode);
1695	}
1696	break;
1697
1698	case GEU:
1699	if (wi::ne_p (const_val, 0))
1700	{
1701	code = GTU;
1702	op1 = immed_wide_int_const (wi::sub (const_val, 1), mode);
1703	}
1704	break;
1705
1706	default:
1707	break;
1708	}
1709	}
1710
1711	if (op0 != XEXP (cond, 0)(((cond)->u.fld[0]).rt_rtx)
1712	\|\| op1 != XEXP (cond, 1)(((cond)->u.fld[1]).rt_rtx)
1713	\|\| code != GET_CODE (cond)((enum rtx_code) (cond)->code)
1714	\|\| GET_MODE (cond)((machine_mode) (cond)->mode) != SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)))
1715	cond = gen_rtx_fmt_ee (code, SImode, op0, op1)gen_rtx_fmt_ee_stat ((code), ((scalar_int_mode ((scalar_int_mode ::from_int) E_SImode))), (op0), (op1) );
1716
1717	return cond;
1718	}
1719
1720	/* Reverses CONDition; returns NULL if we cannot. */
1721
1722	static rtx
1723	reversed_condition (rtx cond)
1724	{
1725	enum rtx_code reversed;
1726	reversed = reversed_comparison_code (cond, NULL__null);
1727	if (reversed == UNKNOWN)
1728	return NULL_RTX(rtx) 0;
1729	else
1730	return gen_rtx_fmt_ee (reversed,gen_rtx_fmt_ee_stat ((reversed), (((machine_mode) (cond)-> mode)), ((((cond)->u.fld[0]).rt_rtx)), ((((cond)->u.fld [1]).rt_rtx)) )
1731	GET_MODE (cond), XEXP (cond, 0),gen_rtx_fmt_ee_stat ((reversed), (((machine_mode) (cond)-> mode)), ((((cond)->u.fld[0]).rt_rtx)), ((((cond)->u.fld [1]).rt_rtx)) )
1732	XEXP (cond, 1))gen_rtx_fmt_ee_stat ((reversed), (((machine_mode) (cond)-> mode)), ((((cond)->u.fld[0]).rt_rtx)), ((((cond)->u.fld [1]).rt_rtx)) );
1733	}
1734
1735	/* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
1736	set of altered regs. */
1737
1738	void
1739	simplify_using_condition (rtx cond, rtx *expr, regset altered)
1740	{
1741	rtx rev, reve, exp = *expr;
1742
1743	/* If some register gets altered later, we do not really speak about its
1744	value at the time of comparison. */
1745	if (altered && altered_reg_used (cond, altered))
1746	return;
1747
1748	if (GET_CODE (cond)((enum rtx_code) (cond)->code) == EQ
1749	&& REG_P (XEXP (cond, 0))(((enum rtx_code) ((((cond)->u.fld[0]).rt_rtx))->code) == REG) && CONSTANT_P (XEXP (cond, 1))((rtx_class[(int) (((enum rtx_code) ((((cond)->u.fld[1]).rt_rtx ))->code))]) == RTX_CONST_OBJ))
1750	{
1751	expr = simplify_replace_rtx (expr, XEXP (cond, 0)(((cond)->u.fld[0]).rt_rtx), XEXP (cond, 1)(((cond)->u.fld[1]).rt_rtx));
1752	return;
1753	}
1754
1755	if (!COMPARISON_P (exp)(((rtx_class[(int) (((enum rtx_code) (exp)->code))]) & (~1)) == (RTX_COMPARE & (~1))))
1756	return;
1757
1758	rev = reversed_condition (cond);
1759	reve = reversed_condition (exp);
1760
1761	cond = canon_condition (cond);
1762	exp = canon_condition (exp);
1763	if (rev)
1764	rev = canon_condition (rev);
1765	if (reve)
1766	reve = canon_condition (reve);
1767
1768	if (rtx_equal_p (exp, cond))
1769	{
1770	*expr = const_true_rtx;
1771	return;
1772	}
1773
1774	if (rev && rtx_equal_p (exp, rev))
1775	{
1776	*expr = const0_rtx(const_int_rtx[64]);
1777	return;
1778	}
1779
1780	if (implies_p (cond, exp))
1781	{
1782	*expr = const_true_rtx;
1783	return;
1784	}
1785
1786	if (reve && implies_p (cond, reve))
1787	{
1788	*expr = const0_rtx(const_int_rtx[64]);
1789	return;
1790	}
1791
1792	/* A proof by contradiction. If EXPR implies (not cond), EXPR must
1793	be false. */
1794	if (rev && implies_p (exp, rev))
1795	{
1796	*expr = const0_rtx(const_int_rtx[64]);
1797	return;
1798	}
1799
1800	/* Similarly, If (not EXPR) implies (not cond), EXPR must be true. */
1801	if (rev && reve && implies_p (reve, rev))
1802	{
1803	*expr = const_true_rtx;
1804	return;
1805	}
1806
1807	/* We would like to have some other tests here. TODO. */
1808
1809	return;
1810	}
1811
1812	/* Use relationship between A and B to eventually eliminate B.
1813	OP is the operation we consider. */
1814
1815	static void
1816	eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
1817	{
1818	switch (op)
1819	{
1820	case AND:
1821	/* If A implies B, we may replace B by true. */
1822	if (implies_p (a, *b))
1823	*b = const_true_rtx;
1824	break;
1825
1826	case IOR:
1827	/* If B implies A, we may replace B by false. */
1828	if (implies_p (*b, a))
1829	*b = const0_rtx(const_int_rtx[64]);
1830	break;
1831
1832	default:
1833	gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 1833, __FUNCTION__));
1834	}
1835	}
1836
1837	/* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
1838	operation we consider. */
1839
1840	static void
1841	eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
1842	{
1843	rtx elt;
1844
1845	for (elt = tail; elt; elt = XEXP (elt, 1)(((elt)->u.fld[1]).rt_rtx))
1846	eliminate_implied_condition (op, *head, &XEXP (elt, 0)(((elt)->u.fld[0]).rt_rtx));
1847	for (elt = tail; elt; elt = XEXP (elt, 1)(((elt)->u.fld[1]).rt_rtx))
1848	eliminate_implied_condition (op, XEXP (elt, 0)(((elt)->u.fld[0]).rt_rtx), head);
1849	}
1850
1851	/* Simplifies EXPR using initial values at the start of the LOOP. If EXPR
1852	is a list, its elements are assumed to be combined using OP. */
1853
1854	static void
1855	simplify_using_initial_values (class loop loop, enum rtx_code op, rtx expr)
1856	{
1857	bool expression_valid;
1858	rtx head, tail, last_valid_expr;
1859	rtx_expr_list *cond_list;
1860	rtx_insn *insn;
1861	rtx neutral, aggr;
1862	regset altered, this_altered;
1863	edge e;
1864
1865	if (!*expr)
1866	return;
1867
1868	if (CONSTANT_P (expr)((rtx_class[(int) (((enum rtx_code) (expr)->code))]) == RTX_CONST_OBJ ))
1869	return;
1870
1871	if (GET_CODE (expr)((enum rtx_code) (expr)->code) == EXPR_LIST)
1872	{
1873	head = XEXP (expr, 0)(((expr)->u.fld[0]).rt_rtx);
1874	tail = XEXP (expr, 1)(((expr)->u.fld[1]).rt_rtx);
1875
1876	eliminate_implied_conditions (op, &head, tail);
1877
1878	switch (op)
1879	{
1880	case AND:
1881	neutral = const_true_rtx;
1882	aggr = const0_rtx(const_int_rtx[64]);
1883	break;
1884
1885	case IOR:
1886	neutral = const0_rtx(const_int_rtx[64]);
1887	aggr = const_true_rtx;
1888	break;
1889
1890	default:
1891	gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 1891, __FUNCTION__));
1892	}
1893
1894	simplify_using_initial_values (loop, UNKNOWN, &head);
1895	if (head == aggr)
1896	{
1897	XEXP (expr, 0)(((expr)->u.fld[0]).rt_rtx) = aggr;
1898	XEXP (expr, 1)(((expr)->u.fld[1]).rt_rtx) = NULL_RTX(rtx) 0;
1899	return;
1900	}
1901	else if (head == neutral)
1902	{
1903	*expr = tail;
1904	simplify_using_initial_values (loop, op, expr);
1905	return;
1906	}
1907	simplify_using_initial_values (loop, op, &tail);
1908
1909	if (tail && XEXP (tail, 0)(((tail)->u.fld[0]).rt_rtx) == aggr)
1910	{
1911	*expr = tail;
1912	return;
1913	}
1914
1915	XEXP (expr, 0)(((expr)->u.fld[0]).rt_rtx) = head;
1916	XEXP (expr, 1)(((expr)->u.fld[1]).rt_rtx) = tail;
1917	return;
1918	}
1919
1920	gcc_assert (op == UNKNOWN)((void)(!(op == UNKNOWN) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 1920, __FUNCTION__), 0 : 0));
1921
1922	replace_single_def_regs (expr);
1923	if (CONSTANT_P (expr)((rtx_class[(int) (((enum rtx_code) (expr)->code))]) == RTX_CONST_OBJ ))
1924	return;
1925
1926	e = loop_preheader_edge (loop);
1927	if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr))
1928	return;
1929
1930	altered = ALLOC_REG_SET (&reg_obstack)bitmap_alloc (&reg_obstack);
1931	this_altered = ALLOC_REG_SET (&reg_obstack)bitmap_alloc (&reg_obstack);
1932
1933	expression_valid = true;
1934	last_valid_expr = *expr;
1935	cond_list = NULL__null;
1936	while (1)
1937	{
1938	insn = BB_END (e->src)(e->src)->il.x.rtl->end_;
1939	if (any_condjump_p (insn) && onlyjump_p (insn))
1940	{
1941	rtx cond = get_condition (BB_END (e->src)(e->src)->il.x.rtl->end_, NULL__null, false, true);
1942
1943	if (cond && (e->flags & EDGE_FALLTHRU))
1944	cond = reversed_condition (cond);
1945	if (cond)
1946	{
1947	rtx old = *expr;
1948	simplify_using_condition (cond, expr, altered);
1949	if (old != *expr)
1950	{
1951	rtx note;
1952	if (CONSTANT_P (expr)((rtx_class[(int) (((enum rtx_code) (expr)->code))]) == RTX_CONST_OBJ ))
1953	goto out;
1954	for (note = cond_list; note; note = XEXP (note, 1)(((note)->u.fld[1]).rt_rtx))
1955	{
1956	simplify_using_condition (XEXP (note, 0)(((note)->u.fld[0]).rt_rtx), expr, altered);
1957	if (CONSTANT_P (expr)((rtx_class[(int) (((enum rtx_code) (expr)->code))]) == RTX_CONST_OBJ ))
1958	goto out;
1959	}
1960	}
1961	cond_list = alloc_EXPR_LIST (0, cond, cond_list);
1962	}
1963	}
1964
1965	FOR_BB_INSNS_REVERSE (e->src, insn)for ((insn) = (e->src)->il.x.rtl->end_; (insn) && (insn) != PREV_INSN ((e->src)->il.x.head_); (insn) = PREV_INSN (insn))
1966	{
1967	rtx src, dest;
1968	rtx old = *expr;
1969
1970	if (!INSN_P (insn)(((((enum rtx_code) (insn)->code) == INSN) \|\| (((enum rtx_code ) (insn)->code) == JUMP_INSN) \|\| (((enum rtx_code) (insn)-> code) == CALL_INSN)) \|\| (((enum rtx_code) (insn)->code) == DEBUG_INSN)))
1971	continue;
1972
1973	CLEAR_REG_SET (this_altered)bitmap_clear (this_altered);
1974	note_stores (insn, mark_altered, this_altered);
1975	if (CALL_P (insn)(((enum rtx_code) (insn)->code) == CALL_INSN))
1976	{
1977	/* Kill all registers that might be clobbered by the call.
1978	We don't track modes of hard registers, so we need to be
1979	conservative and assume that partial kills are full kills. */
1980	function_abi callee_abi = insn_callee_abi (insn);
1981	IOR_REG_SET_HRS (this_altered,bitmap_ior_into (this_altered, bitmap_view<HARD_REG_SET> (callee_abi.full_and_partial_reg_clobbers ()))
1982	callee_abi.full_and_partial_reg_clobbers ())bitmap_ior_into (this_altered, bitmap_view<HARD_REG_SET> (callee_abi.full_and_partial_reg_clobbers ()));
1983	}
1984
1985	if (suitable_set_for_replacement (insn, &dest, &src))
1986	{
1987	rtx_expr_list pnote, pnote_next;
1988
1989	replace_in_expr (expr, dest, src);
1990	if (CONSTANT_P (expr)((rtx_class[(int) (((enum rtx_code) (expr)->code))]) == RTX_CONST_OBJ ))
1991	goto out;
1992
1993	for (pnote = &cond_list; *pnote; pnote = pnote_next)
1994	{
1995	rtx_expr_list note = pnote;
1996	rtx old_cond = XEXP (note, 0)(((note)->u.fld[0]).rt_rtx);
1997
1998	pnote_next = (rtx_expr_list **)&XEXP (note, 1)(((note)->u.fld[1]).rt_rtx);
1999	replace_in_expr (&XEXP (note, 0)(((note)->u.fld[0]).rt_rtx), dest, src);
2000
2001	/* We can no longer use a condition that has been simplified
2002	to a constant, and simplify_using_condition will abort if
2003	we try. */
2004	if (CONSTANT_P (XEXP (note, 0))((rtx_class[(int) (((enum rtx_code) ((((note)->u.fld[0]).rt_rtx ))->code))]) == RTX_CONST_OBJ))
2005	{
2006	pnote = pnote_next;
2007	pnote_next = pnote;
2008	free_EXPR_LIST_node (note);
2009	}
2010	/* Retry simplifications with this condition if either the
2011	expression or the condition changed. */
2012	else if (old_cond != XEXP (note, 0)(((note)->u.fld[0]).rt_rtx) \|\| old != *expr)
2013	simplify_using_condition (XEXP (note, 0)(((note)->u.fld[0]).rt_rtx), expr, altered);
2014	}
2015	}
2016	else
2017	{
2018	rtx_expr_list pnote, pnote_next;
2019
2020	/* If we did not use this insn to make a replacement, any overlap
2021	between stores in this insn and our expression will cause the
2022	expression to become invalid. */
2023	if (altered_reg_used (*expr, this_altered))
2024	goto out;
2025
2026	/* Likewise for the conditions. */
2027	for (pnote = &cond_list; *pnote; pnote = pnote_next)
2028	{
2029	rtx_expr_list note = pnote;
2030	rtx old_cond = XEXP (note, 0)(((note)->u.fld[0]).rt_rtx);
2031
2032	pnote_next = (rtx_expr_list **)&XEXP (note, 1)(((note)->u.fld[1]).rt_rtx);
2033	if (altered_reg_used (old_cond, this_altered))
2034	{
2035	pnote = pnote_next;
2036	pnote_next = pnote;
2037	free_EXPR_LIST_node (note);
2038	}
2039	}
2040	}
2041
2042	if (CONSTANT_P (expr)((rtx_class[(int) (((enum rtx_code) (expr)->code))]) == RTX_CONST_OBJ ))
2043	goto out;
2044
2045	IOR_REG_SET (altered, this_altered)bitmap_ior_into (altered, this_altered);
2046
2047	/* If the expression now contains regs that have been altered, we
2048	can't return it to the caller. However, it is still valid for
2049	further simplification, so keep searching to see if we can
2050	eventually turn it into a constant. */
2051	if (altered_reg_used (*expr, altered))
2052	expression_valid = false;
2053	if (expression_valid)
2054	last_valid_expr = *expr;
2055	}
2056
2057	if (!single_pred_p (e->src)
2058	\|\| single_pred (e->src) == ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr))
2059	break;
2060	e = single_pred_edge (e->src);
2061	}
2062
2063	out:
2064	free_EXPR_LIST_list (&cond_list);
2065	if (!CONSTANT_P (expr)((rtx_class[(int) (((enum rtx_code) (expr)->code))]) == RTX_CONST_OBJ ))
2066	*expr = last_valid_expr;
2067	FREE_REG_SET (altered)((void) (bitmap_obstack_free ((bitmap) altered), (altered) = ( bitmap) __null));
2068	FREE_REG_SET (this_altered)((void) (bitmap_obstack_free ((bitmap) this_altered), (this_altered ) = (bitmap) __null));
2069	}
2070
2071	/* Transforms invariant IV into MODE. Adds assumptions based on the fact
2072	that IV occurs as left operands of comparison COND and its signedness
2073	is SIGNED_P to DESC. */
2074
2075	static void
2076	shorten_into_mode (class rtx_iv *iv, scalar_int_mode mode,
2077	enum rtx_code cond, bool signed_p, class niter_desc *desc)
2078	{
2079	rtx mmin, mmax, cond_over, cond_under;
2080
2081	get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
2082	cond_under = simplify_gen_relational (LT, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), iv->extend_mode,
2083	iv->base, mmin);
2084	cond_over = simplify_gen_relational (GT, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), iv->extend_mode,
2085	iv->base, mmax);
2086
2087	switch (cond)
2088	{
2089	case LE:
2090	case LT:
2091	case LEU:
2092	case LTU:
2093	if (cond_under != const0_rtx(const_int_rtx[64]))
2094	desc->infinite =
2095	alloc_EXPR_LIST (0, cond_under, desc->infinite);
2096	if (cond_over != const0_rtx(const_int_rtx[64]))
2097	desc->noloop_assumptions =
2098	alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
2099	break;
2100
2101	case GE:
2102	case GT:
2103	case GEU:
2104	case GTU:
2105	if (cond_over != const0_rtx(const_int_rtx[64]))
2106	desc->infinite =
2107	alloc_EXPR_LIST (0, cond_over, desc->infinite);
2108	if (cond_under != const0_rtx(const_int_rtx[64]))
2109	desc->noloop_assumptions =
2110	alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
2111	break;
2112
2113	case NE:
2114	if (cond_over != const0_rtx(const_int_rtx[64]))
2115	desc->infinite =
2116	alloc_EXPR_LIST (0, cond_over, desc->infinite);
2117	if (cond_under != const0_rtx(const_int_rtx[64]))
2118	desc->infinite =
2119	alloc_EXPR_LIST (0, cond_under, desc->infinite);
2120	break;
2121
2122	default:
2123	gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 2123, __FUNCTION__));
2124	}
2125
2126	iv->mode = mode;
2127	iv->extend = signed_p ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
2128	}
2129
2130	/* Transforms IV0 and IV1 compared by COND so that they are both compared as
2131	subregs of the same mode if possible (sometimes it is necessary to add
2132	some assumptions to DESC). */
2133
2134	static bool
2135	canonicalize_iv_subregs (class rtx_iv iv0, class rtx_iv iv1,
2136	enum rtx_code cond, class niter_desc *desc)
2137	{
2138	scalar_int_mode comp_mode;
2139	bool signed_p;
2140
2141	/* If the ivs behave specially in the first iteration, or are
2142	added/multiplied after extending, we ignore them. */
2143	if (iv0->first_special \|\| iv0->mult != const1_rtx(const_int_rtx[64 +1]) \|\| iv0->delta != const0_rtx(const_int_rtx[64]))
2144	return false;
2145	if (iv1->first_special \|\| iv1->mult != const1_rtx(const_int_rtx[64 +1]) \|\| iv1->delta != const0_rtx(const_int_rtx[64]))
2146	return false;
2147
2148	/* If there is some extend, it must match signedness of the comparison. */
2149	switch (cond)
2150	{
2151	case LE:
2152	case LT:
2153	if (iv0->extend == IV_ZERO_EXTEND
2154	\|\| iv1->extend == IV_ZERO_EXTEND)
2155	return false;
2156	signed_p = true;
2157	break;
2158
2159	case LEU:
2160	case LTU:
2161	if (iv0->extend == IV_SIGN_EXTEND
2162	\|\| iv1->extend == IV_SIGN_EXTEND)
2163	return false;
2164	signed_p = false;
2165	break;
2166
2167	case NE:
2168	if (iv0->extend != IV_UNKNOWN_EXTEND
2169	&& iv1->extend != IV_UNKNOWN_EXTEND
2170	&& iv0->extend != iv1->extend)
2171	return false;
2172
2173	signed_p = false;
2174	if (iv0->extend != IV_UNKNOWN_EXTEND)
2175	signed_p = iv0->extend == IV_SIGN_EXTEND;
2176	if (iv1->extend != IV_UNKNOWN_EXTEND)
2177	signed_p = iv1->extend == IV_SIGN_EXTEND;
2178	break;
2179
2180	default:
2181	gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 2181, __FUNCTION__));
2182	}
2183
2184	/* Values of both variables should be computed in the same mode. These
2185	might indeed be different, if we have comparison like
2186
2187	(compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2188
2189	and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2190	in different modes. This does not seem impossible to handle, but
2191	it hardly ever occurs in practice.
2192
2193	The only exception is the case when one of operands is invariant.
2194	For example pentium 3 generates comparisons like
2195	(lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
2196	definitely do not want this prevent the optimization. */
2197	comp_mode = iv0->extend_mode;
2198	if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
2199	comp_mode = iv1->extend_mode;
2200
2201	if (iv0->extend_mode != comp_mode)
2202	{
2203	if (iv0->mode != iv0->extend_mode
2204	\|\| iv0->step != const0_rtx(const_int_rtx[64]))
2205	return false;
2206
2207	iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2208	comp_mode, iv0->base, iv0->mode);
2209	iv0->extend_mode = comp_mode;
2210	}
2211
2212	if (iv1->extend_mode != comp_mode)
2213	{
2214	if (iv1->mode != iv1->extend_mode
2215	\|\| iv1->step != const0_rtx(const_int_rtx[64]))
2216	return false;
2217
2218	iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2219	comp_mode, iv1->base, iv1->mode);
2220	iv1->extend_mode = comp_mode;
2221	}
2222
2223	/* Check that both ivs belong to a range of a single mode. If one of the
2224	operands is an invariant, we may need to shorten it into the common
2225	mode. */
2226	if (iv0->mode == iv0->extend_mode
2227	&& iv0->step == const0_rtx(const_int_rtx[64])
2228	&& iv0->mode != iv1->mode)
2229	shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
2230
2231	if (iv1->mode == iv1->extend_mode
2232	&& iv1->step == const0_rtx(const_int_rtx[64])
2233	&& iv0->mode != iv1->mode)
2234	shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
2235
2236	if (iv0->mode != iv1->mode)
2237	return false;
2238
2239	desc->mode = iv0->mode;
2240	desc->signed_p = signed_p;
2241
2242	return true;
2243	}
2244
2245	/* Tries to estimate the maximum number of iterations in LOOP, and return the
2246	result. This function is called from iv_number_of_iterations with
2247	a number of fields in DESC already filled in. OLD_NITER is the original
2248	expression for the number of iterations, before we tried to simplify it. */
2249
2250	static uint64_t
2251	determine_max_iter (class loop loop, class niter_desc desc, rtx old_niter)
2252	{
2253	rtx niter = desc->niter_expr;
2254	rtx mmin, mmax, cmp;
2255	uint64_t nmax, inc;
2256	uint64_t andmax = 0;
2257
2258	/* We used to look for constant operand 0 of AND,
2259	but canonicalization should always make this impossible. */
2260	gcc_checking_assert (GET_CODE (niter) != AND((void)(!(((enum rtx_code) (niter)->code) != AND \|\| !(((enum rtx_code) ((((niter)->u.fld[0]).rt_rtx))->code) == CONST_INT )) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 2261, __FUNCTION__), 0 : 0))
2261	\|\| !CONST_INT_P (XEXP (niter, 0)))((void)(!(((enum rtx_code) (niter)->code) != AND \|\| !(((enum rtx_code) ((((niter)->u.fld[0]).rt_rtx))->code) == CONST_INT )) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 2261, __FUNCTION__), 0 : 0));
2262
2263	if (GET_CODE (niter)((enum rtx_code) (niter)->code) == AND
2264	&& CONST_INT_P (XEXP (niter, 1))(((enum rtx_code) ((((niter)->u.fld[1]).rt_rtx))->code) == CONST_INT))
2265	{
2266	andmax = UINTVAL (XEXP (niter, 1))((unsigned long) (((((niter)->u.fld[1]).rt_rtx))->u.hwint [0]));
2267	niter = XEXP (niter, 0)(((niter)->u.fld[0]).rt_rtx);
2268	}
2269
2270	get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
2271	nmax = UINTVAL (mmax)((unsigned long) ((mmax)->u.hwint[0])) - UINTVAL (mmin)((unsigned long) ((mmin)->u.hwint[0]));
2272
2273	if (GET_CODE (niter)((enum rtx_code) (niter)->code) == UDIV)
2274	{
2275	if (!CONST_INT_P (XEXP (niter, 1))(((enum rtx_code) ((((niter)->u.fld[1]).rt_rtx))->code) == CONST_INT))
2276	return nmax;
2277	inc = INTVAL (XEXP (niter, 1))(((((niter)->u.fld[1]).rt_rtx))->u.hwint[0]);
2278	niter = XEXP (niter, 0)(((niter)->u.fld[0]).rt_rtx);
2279	}
2280	else
2281	inc = 1;
2282
2283	/* We could use a binary search here, but for now improving the upper
2284	bound by just one eliminates one important corner case. */
2285	cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode((void) 0, E_VOIDmode),
2286	desc->mode, old_niter, mmax);
2287	simplify_using_initial_values (loop, UNKNOWN, &cmp);
2288	if (cmp == const_true_rtx)
2289	{
2290	nmax--;
2291
2292	if (dump_file)
2293	fprintf (dump_file, ";; improved upper bound by one.\n");
2294	}
2295	nmax /= inc;
2296	if (andmax)
2297	nmax = MIN (nmax, andmax)((nmax) < (andmax) ? (nmax) : (andmax));
2298	if (dump_file)
2299	fprintf (dump_file, ";; Determined upper bound %" PRId64"l" "d"".\n",
2300	nmax);
2301	return nmax;
2302	}
2303
2304	/* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2305	the result into DESC. Very similar to determine_number_of_iterations
2306	(basically its rtl version), complicated by things like subregs. */
2307
2308	static void
2309	iv_number_of_iterations (class loop loop, rtx_insn insn, rtx condition,
2310	class niter_desc *desc)
2311	{
2312	rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
2313	class rtx_iv iv0, iv1;
2314	rtx assumption, may_not_xform;
2315	enum rtx_code cond;
2316	machine_mode nonvoid_mode;
2317	scalar_int_mode comp_mode;
2318	rtx mmin, mmax, mode_mmin, mode_mmax;
2319	uint64_t s, size, d, inv, max, up, down;
2320	int64_t inc, step_val;
2321	int was_sharp = false;
2322	rtx old_niter;
2323	bool step_is_pow2;
2324
2325	/* The meaning of these assumptions is this:
2326	if !assumptions
2327	then the rest of information does not have to be valid
2328	if noloop_assumptions then the loop does not roll
2329	if infinite then this exit is never used */
2330
2331	desc->assumptions = NULL_RTX(rtx) 0;
2332	desc->noloop_assumptions = NULL_RTX(rtx) 0;
2333	desc->infinite = NULL_RTX(rtx) 0;
2334	desc->simple_p = true;
2335
2336	desc->const_iter = false;
2337	desc->niter_expr = NULL_RTX(rtx) 0;
2338
2339	cond = GET_CODE (condition)((enum rtx_code) (condition)->code);
2340	gcc_assert (COMPARISON_P (condition))((void)(!((((rtx_class[(int) (((enum rtx_code) (condition)-> code))]) & (~1)) == (RTX_COMPARE & (~1)))) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 2340, __FUNCTION__), 0 : 0));
2341
2342	nonvoid_mode = GET_MODE (XEXP (condition, 0))((machine_mode) ((((condition)->u.fld[0]).rt_rtx))->mode );
2343	if (nonvoid_mode == VOIDmode((void) 0, E_VOIDmode))
2344	nonvoid_mode = GET_MODE (XEXP (condition, 1))((machine_mode) ((((condition)->u.fld[1]).rt_rtx))->mode );
2345	/* The constant comparisons should be folded. */
2346	gcc_assert (nonvoid_mode != VOIDmode)((void)(!(nonvoid_mode != ((void) 0, E_VOIDmode)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/loop-iv.c" , 2346, __FUNCTION__), 0 : 0));
2347
2348	/* We only handle integers or pointers. */
2349	scalar_int_mode mode;
2350	if (!is_a <scalar_int_mode> (nonvoid_mode, &mode))
2351	goto fail;
2352
2353	op0 = XEXP (condition, 0)(((condition)->u.fld[0]).rt_rtx);
2354	if (!iv_analyze (insn, mode, op0, &iv0))
2355	goto fail;
2356
2357	op1 = XEXP (condition, 1)(((condition)->u.fld[1]).rt_rtx);
2358	if (!iv_analyze (insn, mode, op1, &iv1))
2359	goto fail;
2360
2361	if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT64
2362	\|\| GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT64)
2363	goto fail;
2364
2365	/* Check condition and normalize it. */
2366
2367	switch (cond)
2368	{
2369	case GE:
2370	case GT:
2371	case GEU:
2372	case GTU:
2373	std::swap (iv0, iv1);
2374	cond = swap_condition (cond);
2375	break;
2376	case NE:
2377	case LE:
2378	case LEU:
2379	case LT:
2380	case LTU:
2381	break;
2382	default:
2383	goto fail;
2384	}
2385
2386	/* Handle extends. This is relatively nontrivial, so we only try in some
2387	easy cases, when we can canonicalize the ivs (possibly by adding some
2388	assumptions) to shape subreg (base + i * step). This function also fills
2389	in desc->mode and desc->signed_p. */
2390
2391	if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2392	goto fail;
2393
2394	comp_mode = iv0.extend_mode;
2395	mode = iv0.mode;
2396	size = GET_MODE_PRECISION (mode);
2397	get_mode_bounds (mode, (cond == LE \|\| cond == LT), comp_mode, &mmin, &mmax);
2398	mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2399	mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2400
2401	if (!CONST_INT_P (iv0.step)(((enum rtx_code) (iv0.step)->code) == CONST_INT) \|\| !CONST_INT_P (iv1.step)(((enum rtx_code) (iv1.step)->code) == CONST_INT))
2402	goto fail;
2403
2404	/* We can take care of the case of two induction variables chasing each other
2405	if the test is NE. I have never seen a loop using it, but still it is
2406	cool. */
2407	if (iv0.step != const0_rtx(const_int_rtx[64]) && iv1.step != const0_rtx(const_int_rtx[64]))
2408	{
2409	if (cond != NE)
2410	goto fail;
2411
2412	iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2413	iv1.step = const0_rtx(const_int_rtx[64]);
2414	}
2415
2416	iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2417	iv1.step = lowpart_subreg (mode, iv1.step, comp_mode);
2418
2419	/* This is either infinite loop or the one that ends immediately, depending
2420	on initial values. Unswitching should remove this kind of conditions. */
2421	if (iv0.step == const0_rtx(const_int_rtx[64]) && iv1.step == const0_rtx(const_int_rtx[64]))
2422	goto fail;
2423
2424	if (cond != NE)
2425	{
2426	if (iv0.step == const0_rtx(const_int_rtx[64]))
2427	step_val = -INTVAL (iv1.step)((iv1.step)->u.hwint[0]);
2428	else
2429	step_val = INTVAL (iv0.step)((iv0.step)->u.hwint[0]);
2430
2431	/* Ignore loops of while (i-- < 10) type. */
2432	if (step_val < 0)
2433	goto fail;
2434
2435	step_is_pow2 = !(step_val & (step_val - 1));
2436	}
2437	else
2438	{
2439	/* We do not care about whether the step is power of two in this
2440	case. */
2441	step_is_pow2 = false;
2442	step_val = 0;
	Value stored to 'step_val' is never read
2443	}
2444
2445	/* Some more condition normalization. We must record some assumptions
2446	due to overflows. */
2447	switch (cond)
2448	{
2449	case LT:
2450	case LTU:
2451	/* We want to take care only of non-sharp relationals; this is easy,
2452	as in cases the overflow would make the transformation unsafe
2453	the loop does not roll. Seemingly it would make more sense to want
2454	to take care of sharp relationals instead, as NE is more similar to
2455	them, but the problem is that here the transformation would be more
2456	difficult due to possibly infinite loops. */
2457	if (iv0.step == const0_rtx(const_int_rtx[64]))
2458	{
2459	tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2460	assumption = simplify_gen_relational (EQ, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, tmp,
2461	mode_mmax);
2462	if (assumption == const_true_rtx)
2463	goto zero_iter_simplify;
2464	iv0.base = simplify_gen_binary (PLUS, comp_mode,
2465	iv0.base, const1_rtx(const_int_rtx[64 +1]));
2466	}
2467	else
2468	{
2469	tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2470	assumption = simplify_gen_relational (EQ, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, tmp,
2471	mode_mmin);
2472	if (assumption == const_true_rtx)
2473	goto zero_iter_simplify;
2474	iv1.base = simplify_gen_binary (PLUS, comp_mode,
2475	iv1.base, constm1_rtx(const_int_rtx[64 -1]));
2476	}
2477
2478	if (assumption != const0_rtx(const_int_rtx[64]))
2479	desc->noloop_assumptions =
2480	alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2481	cond = (cond == LT) ? LE : LEU;
2482
2483	/* It will be useful to be able to tell the difference once more in
2484	LE -> NE reduction. */
2485	was_sharp = true;
2486	break;
2487	default: ;
2488	}
2489
2490	/* Take care of trivially infinite loops. */
2491	if (cond != NE)
2492	{
2493	if (iv0.step == const0_rtx(const_int_rtx[64]))
2494	{
2495	tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2496	if (rtx_equal_p (tmp, mode_mmin))
2497	{
2498	desc->infinite =
2499	alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX(rtx) 0);
2500	/* Fill in the remaining fields somehow. */
2501	goto zero_iter_simplify;
2502	}
2503	}
2504	else
2505	{
2506	tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2507	if (rtx_equal_p (tmp, mode_mmax))
2508	{
2509	desc->infinite =
2510	alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX(rtx) 0);
2511	/* Fill in the remaining fields somehow. */
2512	goto zero_iter_simplify;
2513	}
2514	}
2515	}
2516
2517	/* If we can we want to take care of NE conditions instead of size
2518	comparisons, as they are much more friendly (most importantly
2519	this takes care of special handling of loops with step 1). We can
2520	do it if we first check that upper bound is greater or equal to
2521	lower bound, their difference is constant c modulo step and that
2522	there is not an overflow. */
2523	if (cond != NE)
2524	{
2525	if (iv0.step == const0_rtx(const_int_rtx[64]))
2526	step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2527	else
2528	step = iv0.step;
2529	step = lowpart_subreg (mode, step, comp_mode);
2530	delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2531	delta = lowpart_subreg (mode, delta, comp_mode);
2532	delta = simplify_gen_binary (UMOD, mode, delta, step);
2533	may_xform = const0_rtx(const_int_rtx[64]);
2534	may_not_xform = const_true_rtx;
2535
2536	if (CONST_INT_P (delta)(((enum rtx_code) (delta)->code) == CONST_INT))
2537	{
2538	if (was_sharp && INTVAL (delta)((delta)->u.hwint[0]) == INTVAL (step)((step)->u.hwint[0]) - 1)
2539	{
2540	/* A special case. We have transformed condition of type
2541	for (i = 0; i < 4; i += 4)
2542	into
2543	for (i = 0; i <= 3; i += 4)
2544	obviously if the test for overflow during that transformation
2545	passed, we cannot overflow here. Most importantly any
2546	loop with sharp end condition and step 1 falls into this
2547	category, so handling this case specially is definitely
2548	worth the troubles. */
2549	may_xform = const_true_rtx;
2550	}
2551	else if (iv0.step == const0_rtx(const_int_rtx[64]))
2552	{
2553	bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2554	bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2555	bound = lowpart_subreg (mode, bound, comp_mode);
2556	tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2557	may_xform = simplify_gen_relational (cond, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode,
2558	bound, tmp);
2559	may_not_xform = simplify_gen_relational (reverse_condition (cond),
2560	SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode,
2561	bound, tmp);
2562	}
2563	else
2564	{
2565	bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2566	bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2567	bound = lowpart_subreg (mode, bound, comp_mode);
2568	tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2569	may_xform = simplify_gen_relational (cond, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode,
2570	tmp, bound);
2571	may_not_xform = simplify_gen_relational (reverse_condition (cond),
2572	SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode,
2573	tmp, bound);
2574	}
2575	}
2576
2577	if (may_xform != const0_rtx(const_int_rtx[64]))
2578	{
2579	/* We perform the transformation always provided that it is not
2580	completely senseless. This is OK, as we would need this assumption
2581	to determine the number of iterations anyway. */
2582	if (may_xform != const_true_rtx)
2583	{
2584	/* If the step is a power of two and the final value we have
2585	computed overflows, the cycle is infinite. Otherwise it
2586	is nontrivial to compute the number of iterations. */
2587	if (step_is_pow2)
2588	desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2589	desc->infinite);
2590	else
2591	desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2592	desc->assumptions);
2593	}
2594
2595	/* We are going to lose some information about upper bound on
2596	number of iterations in this step, so record the information
2597	here. */
2598	inc = INTVAL (iv0.step)((iv0.step)->u.hwint[0]) - INTVAL (iv1.step)((iv1.step)->u.hwint[0]);
2599	if (CONST_INT_P (iv1.base)(((enum rtx_code) (iv1.base)->code) == CONST_INT))
2600	up = INTVAL (iv1.base)((iv1.base)->u.hwint[0]);
2601	else
2602	up = INTVAL (mode_mmax)((mode_mmax)->u.hwint[0]) - inc;
2603	down = INTVAL (CONST_INT_P (iv0.base)(((((enum rtx_code) (iv0.base)->code) == CONST_INT) ? iv0. base : mode_mmin)->u.hwint[0])
2604	? iv0.base(((((enum rtx_code) (iv0.base)->code) == CONST_INT) ? iv0. base : mode_mmin)->u.hwint[0])
2605	: mode_mmin)(((((enum rtx_code) (iv0.base)->code) == CONST_INT) ? iv0. base : mode_mmin)->u.hwint[0]);
2606	max = (up - down) / inc + 1;
2607	if (!desc->infinite
2608	&& !desc->assumptions)
2609	record_niter_bound (loop, max, false, true);
2610
2611	if (iv0.step == const0_rtx(const_int_rtx[64]))
2612	{
2613	iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2614	iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2615	}
2616	else
2617	{
2618	iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2619	iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2620	}
2621
2622	tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2623	tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2624	assumption = simplify_gen_relational (reverse_condition (cond),
2625	SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, tmp0, tmp1);
2626	if (assumption == const_true_rtx)
2627	goto zero_iter_simplify;
2628	else if (assumption != const0_rtx(const_int_rtx[64]))
2629	desc->noloop_assumptions =
2630	alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2631	cond = NE;
2632	}
2633	}
2634
2635	/* Count the number of iterations. */
2636	if (cond == NE)
2637	{
2638	/* Everything we do here is just arithmetics modulo size of mode. This
2639	makes us able to do more involved computations of number of iterations
2640	than in other cases. First transform the condition into shape
2641	s * i <> c, with s positive. */
2642	iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2643	iv0.base = const0_rtx(const_int_rtx[64]);
2644	iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2645	iv1.step = const0_rtx(const_int_rtx[64]);
2646	if (INTVAL (iv0.step)((iv0.step)->u.hwint[0]) < 0)
2647	{
2648	iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, comp_mode);
2649	iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, comp_mode);
2650	}
2651	iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2652
2653	/* Let nsd (s, size of mode) = d. If d does not divide c, the loop
2654	is infinite. Otherwise, the number of iterations is
2655	(inverse(s/d) * (c/d)) mod (size of mode/d). */
2656	s = INTVAL (iv0.step)((iv0.step)->u.hwint[0]); d = 1;
2657	while (s % 2 != 1)
2658	{
2659	s /= 2;
2660	d *= 2;
2661	size--;
2662	}
2663	bound = GEN_INT (((uint64_t) 1 << (size - 1 ) << 1) - 1)gen_rtx_CONST_INT (((void) 0, E_VOIDmode), (((uint64_t) 1 << (size - 1 ) << 1) - 1));
2664
2665	tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2666	tmp = simplify_gen_binary (UMOD, mode, tmp1, gen_int_mode (d, mode));
2667	assumption = simplify_gen_relational (NE, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, tmp, const0_rtx(const_int_rtx[64]));
2668	desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2669
2670	tmp = simplify_gen_binary (UDIV, mode, tmp1, gen_int_mode (d, mode));
2671	inv = inverse (s, size);
2672	tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
2673	desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2674	}
2675	else
2676	{
2677	if (iv1.step == const0_rtx(const_int_rtx[64]))
2678	/* Condition in shape a + s * i <= b
2679	We must know that b + s does not overflow and a <= b + s and then we
2680	can compute number of iterations as (b + s - a) / s. (It might
2681	seem that we in fact could be more clever about testing the b + s
2682	overflow condition using some information about b - a mod s,
2683	but it was already taken into account during LE -> NE transform). */
2684	{
2685	step = iv0.step;
2686	tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2687	tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2688
2689	bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2690	lowpart_subreg (mode, step,
2691	comp_mode));
2692	if (step_is_pow2)
2693	{
2694	rtx t0, t1;
2695
2696	/* If s is power of 2, we know that the loop is infinite if
2697	a % s <= b % s and b + s overflows. */
2698	assumption = simplify_gen_relational (reverse_condition (cond),
2699	SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode,
2700	tmp1, bound);
2701
2702	t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2703	t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2704	tmp = simplify_gen_relational (cond, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, t0, t1);
2705	assumption = simplify_gen_binary (AND, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), assumption, tmp);
2706	desc->infinite =
2707	alloc_EXPR_LIST (0, assumption, desc->infinite);
2708	}
2709	else
2710	{
2711	assumption = simplify_gen_relational (cond, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode,
2712	tmp1, bound);
2713	desc->assumptions =
2714	alloc_EXPR_LIST (0, assumption, desc->assumptions);
2715	}
2716
2717	tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2718	tmp = lowpart_subreg (mode, tmp, comp_mode);
2719	assumption = simplify_gen_relational (reverse_condition (cond),
2720	SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, tmp0, tmp);
2721
2722	delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2723	delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2724	}
2725	else
2726	{
2727	/* Condition in shape a <= b - s * i
2728	We must know that a - s does not overflow and a - s <= b and then
2729	we can again compute number of iterations as (b - (a - s)) / s. */
2730	step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2731	tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2732	tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2733
2734	bound = simplify_gen_binary (PLUS, mode, mode_mmin,
2735	lowpart_subreg (mode, step, comp_mode));
2736	if (step_is_pow2)
2737	{
2738	rtx t0, t1;
2739
2740	/* If s is power of 2, we know that the loop is infinite if
2741	a % s <= b % s and a - s overflows. */
2742	assumption = simplify_gen_relational (reverse_condition (cond),
2743	SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode,
2744	bound, tmp0);
2745
2746	t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2747	t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2748	tmp = simplify_gen_relational (cond, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode, t0, t1);
2749	assumption = simplify_gen_binary (AND, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), assumption, tmp);
2750	desc->infinite =
2751	alloc_EXPR_LIST (0, assumption, desc->infinite);
2752	}
2753	else
2754	{
2755	assumption = simplify_gen_relational (cond, SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode,
2756	bound, tmp0);
2757	desc->assumptions =
2758	alloc_EXPR_LIST (0, assumption, desc->assumptions);
2759	}
2760
2761	tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2762	tmp = lowpart_subreg (mode, tmp, comp_mode);
2763	assumption = simplify_gen_relational (reverse_condition (cond),
2764	SImode(scalar_int_mode ((scalar_int_mode::from_int) E_SImode)), mode,
2765	tmp, tmp1);
2766	delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2767	delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2768	}
2769	if (assumption == const_true_rtx)
2770	goto zero_iter_simplify;
2771	else if (assumption != const0_rtx(const_int_rtx[64]))
2772	desc->noloop_assumptions =
2773	alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2774	delta = simplify_gen_binary (UDIV, mode, delta, step);
2775	desc->niter_expr = delta;
2776	}
2777
2778	old_niter = desc->niter_expr;
2779
2780	simplify_using_initial_values (loop, AND, &desc->assumptions);
2781	if (desc->assumptions
2782	&& XEXP (desc->assumptions, 0)(((desc->assumptions)->u.fld[0]).rt_rtx) == const0_rtx(const_int_rtx[64]))
2783	goto fail;
2784	simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2785	simplify_using_initial_values (loop, IOR, &desc->infinite);
2786	simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2787
2788	/* Rerun the simplification. Consider code (created by copying loop headers)
2789
2790	i = 0;
2791
2792	if (0 < n)
2793	{
2794	do
2795	{
2796	i++;
2797	} while (i < n);
2798	}
2799
2800	The first pass determines that i = 0, the second pass uses it to eliminate
2801	noloop assumption. */
2802
2803	simplify_using_initial_values (loop, AND, &desc->assumptions);
2804	if (desc->assumptions
2805	&& XEXP (desc->assumptions, 0)(((desc->assumptions)->u.fld[0]).rt_rtx) == const0_rtx(const_int_rtx[64]))
2806	goto fail;
2807	simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2808	simplify_using_initial_values (loop, IOR, &desc->infinite);
2809	simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2810
2811	if (desc->noloop_assumptions
2812	&& XEXP (desc->noloop_assumptions, 0)(((desc->noloop_assumptions)->u.fld[0]).rt_rtx) == const_true_rtx)
2813	goto zero_iter;
2814
2815	if (CONST_INT_P (desc->niter_expr)(((enum rtx_code) (desc->niter_expr)->code) == CONST_INT ))
2816	{
2817	uint64_t val = INTVAL (desc->niter_expr)((desc->niter_expr)->u.hwint[0]);
2818
2819	desc->const_iter = true;
2820	desc->niter = val & GET_MODE_MASK (desc->mode)mode_mask_array[desc->mode];
2821	if (!desc->infinite
2822	&& !desc->assumptions)
2823	record_niter_bound (loop, desc->niter, false, true);
2824	}
2825	else
2826	{
2827	max = determine_max_iter (loop, desc, old_niter);
2828	if (!max)
2829	goto zero_iter_simplify;
2830	if (!desc->infinite
2831	&& !desc->assumptions)
2832	record_niter_bound (loop, max, false, true);
2833
2834	/* simplify_using_initial_values does a copy propagation on the registers
2835	in the expression for the number of iterations. This prolongs life
2836	ranges of registers and increases register pressure, and usually
2837	brings no gain (and if it happens to do, the cse pass will take care
2838	of it anyway). So prevent this behavior, unless it enabled us to
2839	derive that the number of iterations is a constant. */
2840	desc->niter_expr = old_niter;
2841	}
2842
2843	return;
2844
2845	zero_iter_simplify:
2846	/* Simplify the assumptions. */
2847	simplify_using_initial_values (loop, AND, &desc->assumptions);
2848	if (desc->assumptions
2849	&& XEXP (desc->assumptions, 0)(((desc->assumptions)->u.fld[0]).rt_rtx) == const0_rtx(const_int_rtx[64]))
2850	goto fail;
2851	simplify_using_initial_values (loop, IOR, &desc->infinite);
2852
2853	/* Fallthru. */
2854	zero_iter:
2855	desc->const_iter = true;
2856	desc->niter = 0;
2857	record_niter_bound (loop, 0, true, true);
2858	desc->noloop_assumptions = NULL_RTX(rtx) 0;
2859	desc->niter_expr = const0_rtx(const_int_rtx[64]);
2860	return;
2861
2862	fail:
2863	desc->simple_p = false;
2864	return;
2865	}
2866
2867	/* Checks whether E is a simple exit from LOOP and stores its description
2868	into DESC. */
2869
2870	static void
2871	check_simple_exit (class loop loop, edge e, class niter_desc desc)
2872	{
2873	basic_block exit_bb;
2874	rtx condition;
2875	rtx_insn *at;
2876	edge ein;
2877
2878	exit_bb = e->src;
2879	desc->simple_p = false;
2880
2881	/* It must belong directly to the loop. */
2882	if (exit_bb->loop_father != loop)
2883	return;
2884
2885	/* It must be tested (at least) once during any iteration. */
2886	if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2887	return;
2888
2889	/* It must end in a simple conditional jump. */
2890	if (!any_condjump_p (BB_END (exit_bb)(exit_bb)->il.x.rtl->end_) \|\| !onlyjump_p (BB_END (exit_bb)(exit_bb)->il.x.rtl->end_))
2891	return;
2892
2893	ein = EDGE_SUCC (exit_bb, 0)(*(exit_bb)->succs)[(0)];
2894	if (ein == e)
2895	ein = EDGE_SUCC (exit_bb, 1)(*(exit_bb)->succs)[(1)];
2896
2897	desc->out_edge = e;
2898	desc->in_edge = ein;
2899
2900	/* Test whether the condition is suitable. */
2901	if (!(condition = get_condition (BB_END (ein->src)(ein->src)->il.x.rtl->end_, &at, false, false)))
2902	return;
2903
2904	if (ein->flags & EDGE_FALLTHRU)
2905	{
2906	condition = reversed_condition (condition);
2907	if (!condition)
2908	return;
2909	}
2910
2911	/* Check that we are able to determine number of iterations and fill
2912	in information about it. */
2913	iv_number_of_iterations (loop, at, condition, desc);
2914	}
2915
2916	/* Finds a simple exit of LOOP and stores its description into DESC. */
2917
2918	static void
2919	find_simple_exit (class loop loop, class niter_desc desc)
2920	{
2921	unsigned i;
2922	basic_block *body;
2923	edge e;
2924	class niter_desc act;
2925	bool any = false;
2926	edge_iterator ei;
2927
2928	desc->simple_p = false;
2929	body = get_loop_body (loop);
2930
2931	for (i = 0; i < loop->num_nodes; i++)
2932	{
2933	FOR_EACH_EDGE (e, ei, body[i]->succs)for ((ei) = ei_start_1 (&((body[i]->succs))); ei_cond ( (ei), &(e)); ei_next (&(ei)))
2934	{
2935	if (flow_bb_inside_loop_p (loop, e->dest))
2936	continue;
2937
2938	check_simple_exit (loop, e, &act);
2939	if (!act.simple_p)
2940	continue;
2941
2942	if (!any)
2943	any = true;
2944	else
2945	{
2946	/* Prefer constant iterations; the less the better. */
2947	if (!act.const_iter
2948	\|\| (desc->const_iter && act.niter >= desc->niter))
2949	continue;
2950
2951	/* Also if the actual exit may be infinite, while the old one
2952	not, prefer the old one. */
2953	if (act.infinite && !desc->infinite)
2954	continue;
2955	}
2956
2957	*desc = act;
2958	}
2959	}
2960
2961	if (dump_file)
2962	{
2963	if (desc->simple_p)
2964	{
2965	fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2966	fprintf (dump_file, " simple exit %d -> %d\n",
2967	desc->out_edge->src->index,
2968	desc->out_edge->dest->index);
2969	if (desc->assumptions)
2970	{
2971	fprintf (dump_file, " assumptions: ");
2972	print_rtl (dump_file, desc->assumptions);
2973	fprintf (dump_file, "\n");
2974	}
2975	if (desc->noloop_assumptions)
2976	{
2977	fprintf (dump_file, " does not roll if: ");
2978	print_rtl (dump_file, desc->noloop_assumptions);
2979	fprintf (dump_file, "\n");
2980	}
2981	if (desc->infinite)
2982	{
2983	fprintf (dump_file, " infinite if: ");
2984	print_rtl (dump_file, desc->infinite);
2985	fprintf (dump_file, "\n");
2986	}
2987
2988	fprintf (dump_file, " number of iterations: ");
2989	print_rtl (dump_file, desc->niter_expr);
2990	fprintf (dump_file, "\n");
2991
2992	fprintf (dump_file, " upper bound: %li\n",
2993	(long)get_max_loop_iterations_int (loop));
2994	fprintf (dump_file, " likely upper bound: %li\n",
2995	(long)get_likely_max_loop_iterations_int (loop));
2996	fprintf (dump_file, " realistic bound: %li\n",
2997	(long)get_estimated_loop_iterations_int (loop));
2998	}
2999	else
3000	fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
3001	}
3002
3003	/* Fix up the finiteness if possible. We can only do it for single exit,
3004	since the loop is finite, but it's possible that we predicate one loop
3005	exit to be finite which can not be determined as finite in middle-end as
3006	well. It results in incorrect predicate information on the exit condition
3007	expression. For example, if says [(int) _1 + -8, + , -8] != 0 finite,
3008	it means _1 can exactly divide -8. */
3009	if (desc->infinite && single_exit (loop) && finite_loop_p (loop))
3010	{
3011	desc->infinite = NULL_RTX(rtx) 0;
3012	if (dump_file)
3013	fprintf (dump_file, " infinite updated to finite.\n");
3014	}
3015
3016	free (body);
3017	}
3018
3019	/* Creates a simple loop description of LOOP if it was not computed
3020	already. */
3021
3022	class niter_desc *
3023	get_simple_loop_desc (class loop *loop)
3024	{
3025	class niter_desc *desc = simple_loop_desc (loop);
3026
3027	if (desc)
3028	return desc;
3029
3030	/* At least desc->infinite is not always initialized by
3031	find_simple_loop_exit. */
3032	desc = ggc_cleared_alloc<niter_desc> ();
3033	iv_analysis_loop_init (loop);
3034	find_simple_exit (loop, desc);
3035	loop->simple_loop_desc = desc;
3036	return desc;
3037	}
3038
3039	/* Releases simple loop description for LOOP. */
3040
3041	void
3042	free_simple_loop_desc (class loop *loop)
3043	{
3044	class niter_desc *desc = simple_loop_desc (loop);
3045
3046	if (!desc)
3047	return;
3048
3049	ggc_free (desc);
3050	loop->simple_loop_desc = NULL__null;
3051	}