1	/* Conditional constant propagation pass for the GNU compiler.
2	Copyright (C) 2000-2023 Free Software Foundation, Inc.
3	Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>
4	Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>
5
6	This file is part of GCC.
7
8	GCC is free software; you can redistribute it and/or modify it
9	under the terms of the GNU General Public License as published by the
10	Free Software Foundation; either version 3, or (at your option) any
11	later version.
12
13	GCC is distributed in the hope that it will be useful, but WITHOUT
14	ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16	for more details.
17
18	You should have received a copy of the GNU General Public License
19	along with GCC; see the file COPYING3. If not see
20	<http://www.gnu.org/licenses/>. */
21
22	/* Conditional constant propagation (CCP) is based on the SSA
23	propagation engine (tree-ssa-propagate.cc). Constant assignments of
24	the form VAR = CST are propagated from the assignments into uses of
25	VAR, which in turn may generate new constants. The simulation uses
26	a four level lattice to keep track of constant values associated
27	with SSA names. Given an SSA name V_i, it may take one of the
28	following values:
29
30	UNINITIALIZED -> the initial state of the value. This value
31	is replaced with a correct initial value
32	the first time the value is used, so the
33	rest of the pass does not need to care about
34	it. Using this value simplifies initialization
35	of the pass, and prevents us from needlessly
36	scanning statements that are never reached.
37
38	UNDEFINED -> V_i is a local variable whose definition
39	has not been processed yet. Therefore we
40	don't yet know if its value is a constant
41	or not.
42
43	CONSTANT -> V_i has been found to hold a constant
44	value C.
45
46	VARYING -> V_i cannot take a constant value, or if it
47	does, it is not possible to determine it
48	at compile time.
49
50	The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node:
51
52	1- In ccp_visit_stmt, we are interested in assignments whose RHS
53	evaluates into a constant and conditional jumps whose predicate
54	evaluates into a boolean true or false. When an assignment of
55	the form V_i = CONST is found, V_i's lattice value is set to
56	CONSTANT and CONST is associated with it. This causes the
57	propagation engine to add all the SSA edges coming out the
58	assignment into the worklists, so that statements that use V_i
59	can be visited.
60
61	If the statement is a conditional with a constant predicate, we
62	mark the outgoing edges as executable or not executable
63	depending on the predicate's value. This is then used when
64	visiting PHI nodes to know when a PHI argument can be ignored.
65
66
67	2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the
68	same constant C, then the LHS of the PHI is set to C. This
69	evaluation is known as the "meet operation". Since one of the
70	goals of this evaluation is to optimistically return constant
71	values as often as possible, it uses two main short cuts:
72
73	- If an argument is flowing in through a non-executable edge, it
74	is ignored. This is useful in cases like this:
75
76	if (PRED)
77	a_9 = 3;
78	else
79	a_10 = 100;
80	a_11 = PHI (a_9, a_10)
81
82	If PRED is known to always evaluate to false, then we can
83	assume that a_11 will always take its value from a_10, meaning
84	that instead of consider it VARYING (a_9 and a_10 have
85	different values), we can consider it CONSTANT 100.
86
87	- If an argument has an UNDEFINED value, then it does not affect
88	the outcome of the meet operation. If a variable V_i has an
89	UNDEFINED value, it means that either its defining statement
90	hasn't been visited yet or V_i has no defining statement, in
91	which case the original symbol 'V' is being used
92	uninitialized. Since 'V' is a local variable, the compiler
93	may assume any initial value for it.
94
95
96	After propagation, every variable V_i that ends up with a lattice
97	value of CONSTANT will have the associated constant value in the
98	array CONST_VAL[i].VALUE. That is fed into substitute_and_fold for
99	final substitution and folding.
100
101	This algorithm uses wide-ints at the max precision of the target.
102	This means that, with one uninteresting exception, variables with
103	UNSIGNED types never go to VARYING because the bits above the
104	precision of the type of the variable are always zero. The
105	uninteresting case is a variable of UNSIGNED type that has the
106	maximum precision of the target. Such variables can go to VARYING,
107	but this causes no loss of infomation since these variables will
108	never be extended.
109
110	References:
111
112	Constant propagation with conditional branches,
113	Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
114
115	Building an Optimizing Compiler,
116	Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
117
118	Advanced Compiler Design and Implementation,
119	Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
120
121	#include "config.h"
122	#include "system.h"
123	#include "coretypes.h"
124	#include "backend.h"
125	#include "target.h"
126	#include "tree.h"
127	#include "gimple.h"
128	#include "tree-pass.h"
129	#include "ssa.h"
130	#include "gimple-pretty-print.h"
131	#include "fold-const.h"
132	#include "gimple-iterator.h"
133	#include "gimple-fold.h"
134	#include "tree-eh.h"
135	#include "gimplify.h"
136	#include "tree-cfg.h"
137	#include "tree-ssa-propagate.h"
138	#include "dbgcnt.h"
139	#include "builtins.h"
140	#include "cfgloop.h"
141	#include "stor-layout.h"
142	#include "optabs-query.h"
143	#include "tree-ssa-ccp.h"
144	#include "tree-dfa.h"
145	#include "diagnostic-core.h"
146	#include "stringpool.h"
147	#include "attribs.h"
148	#include "tree-vector-builder.h"
149	#include "cgraph.h"
150	#include "alloc-pool.h"
151	#include "symbol-summary.h"
152	#include "ipa-utils.h"
153	#include "ipa-prop.h"
154	#include "internal-fn.h"
155
156	/* Possible lattice values. */
157	typedef enum
158	{
159	UNINITIALIZED,
160	UNDEFINED,
161	CONSTANT,
162	VARYING
163	} ccp_lattice_t;
164
165	class ccp_prop_value_t {
166	public:
167	/* Lattice value. */
168	ccp_lattice_t lattice_val;
169
170	/* Propagated value. */
171	tree value;
172
173	/* Mask that applies to the propagated value during CCP. For X
174	with a CONSTANT lattice value X & ~mask == value & ~mask. The
175	zero bits in the mask cover constant values. The ones mean no
176	information. */
177	widest_int mask;
178	};
179
180	class ccp_propagate : public ssa_propagation_engine
181	{
182	public:
183	enum ssa_prop_result visit_stmt (gimple *, edge *, tree *) final override;
184	enum ssa_prop_result visit_phi (gphi *) final override;
185	};
186
187	/* Array of propagated constant values. After propagation,
188	CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If
189	the constant is held in an SSA name representing a memory store
190	(i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual
191	memory reference used to store (i.e., the LHS of the assignment
192	doing the store). */
193	static ccp_prop_value_t *const_val;
194	static unsigned n_const_val;
195
196	static void canonicalize_value (ccp_prop_value_t *);
197	static void ccp_lattice_meet (ccp_prop_value_t *, ccp_prop_value_t *);
198
199	/* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */
200
201	static void
202	dump_lattice_value (FILE *outf, const char *prefix, ccp_prop_value_t val)
203	{
204	switch (val.lattice_val)
205	{
206	case UNINITIALIZED:
207	fprintf (stream: outf, format: "%sUNINITIALIZED", prefix);
208	break;
209	case UNDEFINED:
210	fprintf (stream: outf, format: "%sUNDEFINED", prefix);
211	break;
212	case VARYING:
213	fprintf (stream: outf, format: "%sVARYING", prefix);
214	break;
215	case CONSTANT:
216	if (TREE_CODE (val.value) != INTEGER_CST
217	|| val.mask == 0)
218	{
219	fprintf (stream: outf, format: "%sCONSTANT ", prefix);
220	print_generic_expr (outf, val.value, dump_flags);
221	}
222	else
223	{
224	widest_int cval = wi::bit_and_not (x: wi::to_widest (t: val.value),
225	y: val.mask);
226	fprintf (stream: outf, format: "%sCONSTANT ", prefix);
227	print_hex (wi: cval, file: outf);
228	fprintf (stream: outf, format: " (");
229	print_hex (wi: val.mask, file: outf);
230	fprintf (stream: outf, format: ")");
231	}
232	break;
233	default:
234	gcc_unreachable ();
235	}
236	}
237
238
239	/* Print lattice value VAL to stderr. */
240
241	void debug_lattice_value (ccp_prop_value_t val);
242
243	DEBUG_FUNCTION void
244	debug_lattice_value (ccp_prop_value_t val)
245	{
246	dump_lattice_value (stderr, prefix: "", val);
247	fprintf (stderr, format: "\n");
248	}
249
250	/* Extend NONZERO_BITS to a full mask, based on sgn. */
251
252	static widest_int
253	extend_mask (const wide_int &nonzero_bits, signop sgn)
254	{
255	return widest_int::from (x: nonzero_bits, sgn);
256	}
257
258	/* Compute a default value for variable VAR and store it in the
259	CONST_VAL array. The following rules are used to get default
260	values:
261
262	1- Global and static variables that are declared constant are
263	considered CONSTANT.
264
265	2- Any other value is considered UNDEFINED. This is useful when
266	considering PHI nodes. PHI arguments that are undefined do not
267	change the constant value of the PHI node, which allows for more
268	constants to be propagated.
269
270	3- Variables defined by statements other than assignments and PHI
271	nodes are considered VARYING.
272
273	4- Initial values of variables that are not GIMPLE registers are
274	considered VARYING. */
275
276	static ccp_prop_value_t
277	get_default_value (tree var)
278	{
279	ccp_prop_value_t val = { .lattice_val: UNINITIALIZED, NULL_TREE, .mask: 0 };
280	gimple *stmt;
281
282	stmt = SSA_NAME_DEF_STMT (var);
283
284	if (gimple_nop_p (g: stmt))
285	{
286	/* Variables defined by an empty statement are those used
287	before being initialized. If VAR is a local variable, we
288	can assume initially that it is UNDEFINED, otherwise we must
289	consider it VARYING. */
290	if (!virtual_operand_p (op: var)
291	&& SSA_NAME_VAR (var)
292	&& VAR_P (SSA_NAME_VAR (var)))
293	val.lattice_val = UNDEFINED;
294	else
295	{
296	val.lattice_val = VARYING;
297	val.mask = -1;
298	if (flag_tree_bit_ccp)
299	{
300	wide_int nonzero_bits = get_nonzero_bits (var);
301	tree value;
302	widest_int mask;
303
304	if (SSA_NAME_VAR (var)
305	&& TREE_CODE (SSA_NAME_VAR (var)) == PARM_DECL
306	&& ipcp_get_parm_bits (SSA_NAME_VAR (var), &value, &mask))
307	{
308	val.lattice_val = CONSTANT;
309	val.value = value;
310	widest_int ipa_value = wi::to_widest (t: value);
311	/* Unknown bits from IPA CP must be equal to zero. */
312	gcc_assert (wi::bit_and (ipa_value, mask) == 0);
313	val.mask = mask;
314	if (nonzero_bits != -1)
315	val.mask &= extend_mask (nonzero_bits,
316	TYPE_SIGN (TREE_TYPE (var)));
317	}
318	else if (nonzero_bits != -1)
319	{
320	val.lattice_val = CONSTANT;
321	val.value = build_zero_cst (TREE_TYPE (var));
322	val.mask = extend_mask (nonzero_bits,
323	TYPE_SIGN (TREE_TYPE (var)));
324	}
325	}
326	}
327	}
328	else if (is_gimple_assign (gs: stmt))
329	{
330	tree cst;
331	if (gimple_assign_single_p (gs: stmt)
332	&& DECL_P (gimple_assign_rhs1 (stmt))
333	&& (cst = get_symbol_constant_value (gimple_assign_rhs1 (gs: stmt))))
334	{
335	val.lattice_val = CONSTANT;
336	val.value = cst;
337	}
338	else
339	{
340	/* Any other variable defined by an assignment is considered
341	UNDEFINED. */
342	val.lattice_val = UNDEFINED;
343	}
344	}
345	else if ((is_gimple_call (gs: stmt)
346	&& gimple_call_lhs (gs: stmt) != NULL_TREE)
347	|| gimple_code (g: stmt) == GIMPLE_PHI)
348	{
349	/* A variable defined by a call or a PHI node is considered
350	UNDEFINED. */
351	val.lattice_val = UNDEFINED;
352	}
353	else
354	{
355	/* Otherwise, VAR will never take on a constant value. */
356	val.lattice_val = VARYING;
357	val.mask = -1;
358	}
359
360	return val;
361	}
362
363
364	/* Get the constant value associated with variable VAR. */
365
366	static inline ccp_prop_value_t *
367	get_value (tree var)
368	{
369	ccp_prop_value_t *val;
370
371	if (const_val == NULL
372	|| SSA_NAME_VERSION (var) >= n_const_val)
373	return NULL;
374
375	val = &const_val[SSA_NAME_VERSION (var)];
376	if (val->lattice_val == UNINITIALIZED)
377	*val = get_default_value (var);
378
379	canonicalize_value (val);
380
381	return val;
382	}
383
384	/* Return the constant tree value associated with VAR. */
385
386	static inline tree
387	get_constant_value (tree var)
388	{
389	ccp_prop_value_t *val;
390	if (TREE_CODE (var) != SSA_NAME)
391	{
392	if (is_gimple_min_invariant (var))
393	return var;
394	return NULL_TREE;
395	}
396	val = get_value (var);
397	if (val
398	&& val->lattice_val == CONSTANT
399	&& (TREE_CODE (val->value) != INTEGER_CST
400	|| val->mask == 0))
401	return val->value;
402	return NULL_TREE;
403	}
404
405	/* Sets the value associated with VAR to VARYING. */
406
407	static inline void
408	set_value_varying (tree var)
409	{
410	ccp_prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
411
412	val->lattice_val = VARYING;
413	val->value = NULL_TREE;
414	val->mask = -1;
415	}
416
417	/* For integer constants, make sure to drop TREE_OVERFLOW. */
418
419	static void
420	canonicalize_value (ccp_prop_value_t *val)
421	{
422	if (val->lattice_val != CONSTANT)
423	return;
424
425	if (TREE_OVERFLOW_P (val->value))
426	val->value = drop_tree_overflow (val->value);
427	}
428
429	/* Return whether the lattice transition is valid. */
430
431	static bool
432	valid_lattice_transition (ccp_prop_value_t old_val, ccp_prop_value_t new_val)
433	{
434	/* Lattice transitions must always be monotonically increasing in
435	value. */
436	if (old_val.lattice_val < new_val.lattice_val)
437	return true;
438
439	if (old_val.lattice_val != new_val.lattice_val)
440	return false;
441
442	if (!old_val.value && !new_val.value)
443	return true;
444
445	/* Now both lattice values are CONSTANT. */
446
447	/* Allow arbitrary copy changes as we might look through PHI <a_1, ...>
448	when only a single copy edge is executable. */
449	if (TREE_CODE (old_val.value) == SSA_NAME
450	&& TREE_CODE (new_val.value) == SSA_NAME)
451	return true;
452
453	/* Allow transitioning from a constant to a copy. */
454	if (is_gimple_min_invariant (old_val.value)
455	&& TREE_CODE (new_val.value) == SSA_NAME)
456	return true;
457
458	/* Allow transitioning from PHI <&x, not executable> == &x
459	to PHI <&x, &y> == common alignment. */
460	if (TREE_CODE (old_val.value) != INTEGER_CST
461	&& TREE_CODE (new_val.value) == INTEGER_CST)
462	return true;
463
464	/* Bit-lattices have to agree in the still valid bits. */
465	if (TREE_CODE (old_val.value) == INTEGER_CST
466	&& TREE_CODE (new_val.value) == INTEGER_CST)
467	return (wi::bit_and_not (x: wi::to_widest (t: old_val.value), y: new_val.mask)
468	== wi::bit_and_not (x: wi::to_widest (t: new_val.value), y: new_val.mask));
469
470	/* Otherwise constant values have to agree. */
471	if (operand_equal_p (old_val.value, new_val.value, flags: 0))
472	return true;
473
474	/* At least the kinds and types should agree now. */
475	if (TREE_CODE (old_val.value) != TREE_CODE (new_val.value)
476	|| !types_compatible_p (TREE_TYPE (old_val.value),
477	TREE_TYPE (new_val.value)))
478	return false;
479
480	/* For floats and !HONOR_NANS allow transitions from (partial) NaN
481	to non-NaN. */
482	tree type = TREE_TYPE (new_val.value);
483	if (SCALAR_FLOAT_TYPE_P (type)
484	&& !HONOR_NANS (type))
485	{
486	if (REAL_VALUE_ISNAN (TREE_REAL_CST (old_val.value)))
487	return true;
488	}
489	else if (VECTOR_FLOAT_TYPE_P (type)
490	&& !HONOR_NANS (type))
491	{
492	unsigned int count
493	= tree_vector_builder::binary_encoded_nelts (vec1: old_val.value,
494	vec2: new_val.value);
495	for (unsigned int i = 0; i < count; ++i)
496	if (!REAL_VALUE_ISNAN
497	(TREE_REAL_CST (VECTOR_CST_ENCODED_ELT (old_val.value, i)))
498	&& !operand_equal_p (VECTOR_CST_ENCODED_ELT (old_val.value, i),
499	VECTOR_CST_ENCODED_ELT (new_val.value, i), flags: 0))
500	return false;
501	return true;
502	}
503	else if (COMPLEX_FLOAT_TYPE_P (type)
504	&& !HONOR_NANS (type))
505	{
506	if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_REALPART (old_val.value)))
507	&& !operand_equal_p (TREE_REALPART (old_val.value),
508	TREE_REALPART (new_val.value), flags: 0))
509	return false;
510	if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_IMAGPART (old_val.value)))
511	&& !operand_equal_p (TREE_IMAGPART (old_val.value),
512	TREE_IMAGPART (new_val.value), flags: 0))
513	return false;
514	return true;
515	}
516	return false;
517	}
518
519	/* Set the value for variable VAR to NEW_VAL. Return true if the new
520	value is different from VAR's previous value. */
521
522	static bool
523	set_lattice_value (tree var, ccp_prop_value_t *new_val)
524	{
525	/* We can deal with old UNINITIALIZED values just fine here. */
526	ccp_prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)];
527
528	canonicalize_value (val: new_val);
529
530	/* We have to be careful to not go up the bitwise lattice
531	represented by the mask. Instead of dropping to VARYING
532	use the meet operator to retain a conservative value.
533	Missed optimizations like PR65851 makes this necessary.
534	It also ensures we converge to a stable lattice solution. */
535	if (old_val->lattice_val != UNINITIALIZED
536	/* But avoid using meet for constant -> copy transitions. */
537	&& !(old_val->lattice_val == CONSTANT
538	&& CONSTANT_CLASS_P (old_val->value)
539	&& new_val->lattice_val == CONSTANT
540	&& TREE_CODE (new_val->value) == SSA_NAME))
541	ccp_lattice_meet (new_val, old_val);
542
543	gcc_checking_assert (valid_lattice_transition (*old_val, *new_val));
544
545	/* If *OLD_VAL and NEW_VAL are the same, return false to inform the
546	caller that this was a non-transition. */
547	if (old_val->lattice_val != new_val->lattice_val
548	|| (new_val->lattice_val == CONSTANT
549	&& (TREE_CODE (new_val->value) != TREE_CODE (old_val->value)
550	|| (TREE_CODE (new_val->value) == INTEGER_CST
551	&& (new_val->mask != old_val->mask
552	|| (wi::bit_and_not (x: wi::to_widest (t: old_val->value),
553	y: new_val->mask)
554	!= wi::bit_and_not (x: wi::to_widest (t: new_val->value),
555	y: new_val->mask))))
556	|| (TREE_CODE (new_val->value) != INTEGER_CST
557	&& !operand_equal_p (new_val->value, old_val->value, flags: 0)))))
558	{
559	/* ??? We would like to delay creation of INTEGER_CSTs from
560	partially constants here. */
561
562	if (dump_file && (dump_flags & TDF_DETAILS))
563	{
564	dump_lattice_value (outf: dump_file, prefix: "Lattice value changed to ", val: *new_val);
565	fprintf (stream: dump_file, format: ". Adding SSA edges to worklist.\n");
566	}
567
568	*old_val = *new_val;
569
570	gcc_assert (new_val->lattice_val != UNINITIALIZED);
571	return true;
572	}
573
574	return false;
575	}
576
577	static ccp_prop_value_t get_value_for_expr (tree, bool);
578	static ccp_prop_value_t bit_value_binop (enum tree_code, tree, tree, tree);
579	void bit_value_binop (enum tree_code, signop, int, widest_int *, widest_int *,
580	signop, int, const widest_int &, const widest_int &,
581	signop, int, const widest_int &, const widest_int &);
582
583	/* Return a widest_int that can be used for bitwise simplifications
584	from VAL. */
585
586	static widest_int
587	value_to_wide_int (ccp_prop_value_t val)
588	{
589	if (val.value
590	&& TREE_CODE (val.value) == INTEGER_CST)
591	return wi::to_widest (t: val.value);
592
593	return 0;
594	}
595
596	/* Return the value for the address expression EXPR based on alignment
597	information. */
598
599	static ccp_prop_value_t
600	get_value_from_alignment (tree expr)
601	{
602	tree type = TREE_TYPE (expr);
603	ccp_prop_value_t val;
604	unsigned HOST_WIDE_INT bitpos;
605	unsigned int align;
606
607	gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
608
609	get_pointer_alignment_1 (expr, &align, &bitpos);
610	val.mask = wi::bit_and_not
611	(POINTER_TYPE_P (type) || TYPE_UNSIGNED (type)
612	? wi::mask <widest_int> (TYPE_PRECISION (type), negate_p: false)
613	: -1,
614	y: align / BITS_PER_UNIT - 1);
615	val.lattice_val
616	= wi::sext (x: val.mask, TYPE_PRECISION (type)) == -1 ? VARYING : CONSTANT;
617	if (val.lattice_val == CONSTANT)
618	val.value = build_int_cstu (type, bitpos / BITS_PER_UNIT);
619	else
620	val.value = NULL_TREE;
621
622	return val;
623	}
624
625	/* Return the value for the tree operand EXPR. If FOR_BITS_P is true
626	return constant bits extracted from alignment information for
627	invariant addresses. */
628
629	static ccp_prop_value_t
630	get_value_for_expr (tree expr, bool for_bits_p)
631	{
632	ccp_prop_value_t val;
633
634	if (TREE_CODE (expr) == SSA_NAME)
635	{
636	ccp_prop_value_t *val_ = get_value (var: expr);
637	if (val_)
638	val = *val_;
639	else
640	{
641	val.lattice_val = VARYING;
642	val.value = NULL_TREE;
643	val.mask = -1;
644	}
645	if (for_bits_p
646	&& val.lattice_val == CONSTANT)
647	{
648	if (TREE_CODE (val.value) == ADDR_EXPR)
649	val = get_value_from_alignment (expr: val.value);
650	else if (TREE_CODE (val.value) != INTEGER_CST)
651	{
652	val.lattice_val = VARYING;
653	val.value = NULL_TREE;
654	val.mask = -1;
655	}
656	}
657	/* Fall back to a copy value. */
658	if (!for_bits_p
659	&& val.lattice_val == VARYING
660	&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr))
661	{
662	val.lattice_val = CONSTANT;
663	val.value = expr;
664	val.mask = -1;
665	}
666	}
667	else if (is_gimple_min_invariant (expr)
668	&& (!for_bits_p || TREE_CODE (expr) == INTEGER_CST))
669	{
670	val.lattice_val = CONSTANT;
671	val.value = expr;
672	val.mask = 0;
673	canonicalize_value (val: &val);
674	}
675	else if (TREE_CODE (expr) == ADDR_EXPR)
676	val = get_value_from_alignment (expr);
677	else
678	{
679	val.lattice_val = VARYING;
680	val.mask = -1;
681	val.value = NULL_TREE;
682	}
683
684	if (val.lattice_val == VARYING
685	&& INTEGRAL_TYPE_P (TREE_TYPE (expr))
686	&& TYPE_UNSIGNED (TREE_TYPE (expr)))
687	val.mask = wi::zext (x: val.mask, TYPE_PRECISION (TREE_TYPE (expr)));
688
689	return val;
690	}
691
692	/* Return the likely CCP lattice value for STMT.
693
694	If STMT has no operands, then return CONSTANT.
695
696	Else if undefinedness of operands of STMT cause its value to be
697	undefined, then return UNDEFINED.
698
699	Else if any operands of STMT are constants, then return CONSTANT.
700
701	Else return VARYING. */
702
703	static ccp_lattice_t
704	likely_value (gimple *stmt)
705	{
706	bool has_constant_operand, has_undefined_operand, all_undefined_operands;
707	bool has_nsa_operand;
708	tree use;
709	ssa_op_iter iter;
710	unsigned i;
711
712	enum gimple_code code = gimple_code (g: stmt);
713
714	/* This function appears to be called only for assignments, calls,
715	conditionals, and switches, due to the logic in visit_stmt. */
716	gcc_assert (code == GIMPLE_ASSIGN
717	|| code == GIMPLE_CALL
718	|| code == GIMPLE_COND
719	|| code == GIMPLE_SWITCH);
720
721	/* If the statement has volatile operands, it won't fold to a
722	constant value. */
723	if (gimple_has_volatile_ops (stmt))
724	return VARYING;
725
726	/* .DEFERRED_INIT produces undefined. */
727	if (gimple_call_internal_p (gs: stmt, fn: IFN_DEFERRED_INIT))
728	return UNDEFINED;
729
730	/* Arrive here for more complex cases. */
731	has_constant_operand = false;
732	has_undefined_operand = false;
733	all_undefined_operands = true;
734	has_nsa_operand = false;
735	FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
736	{
737	ccp_prop_value_t *val = get_value (var: use);
738
739	if (val && val->lattice_val == UNDEFINED)
740	has_undefined_operand = true;
741	else
742	all_undefined_operands = false;
743
744	if (val && val->lattice_val == CONSTANT)
745	has_constant_operand = true;
746
747	if (SSA_NAME_IS_DEFAULT_DEF (use)
748	|| !prop_simulate_again_p (SSA_NAME_DEF_STMT (use)))
749	has_nsa_operand = true;
750	}
751
752	/* There may be constants in regular rhs operands. For calls we
753	have to ignore lhs, fndecl and static chain, otherwise only
754	the lhs. */
755	for (i = (is_gimple_call (gs: stmt) ? 2 : 0) + gimple_has_lhs (stmt);
756	i < gimple_num_ops (gs: stmt); ++i)
757	{
758	tree op = gimple_op (gs: stmt, i);
759	if (!op || TREE_CODE (op) == SSA_NAME)
760	continue;
761	if (is_gimple_min_invariant (op))
762	has_constant_operand = true;
763	}
764
765	if (has_constant_operand)
766	all_undefined_operands = false;
767
768	if (has_undefined_operand
769	&& code == GIMPLE_CALL
770	&& gimple_call_internal_p (gs: stmt))
771	switch (gimple_call_internal_fn (gs: stmt))
772	{
773	/* These 3 builtins use the first argument just as a magic
774	way how to find out a decl uid. */
775	case IFN_GOMP_SIMD_LANE:
776	case IFN_GOMP_SIMD_VF:
777	case IFN_GOMP_SIMD_LAST_LANE:
778	has_undefined_operand = false;
779	break;
780	default:
781	break;
782	}
783
784	/* If the operation combines operands like COMPLEX_EXPR make sure to
785	not mark the result UNDEFINED if only one part of the result is
786	undefined. */
787	if (has_undefined_operand && all_undefined_operands)
788	return UNDEFINED;
789	else if (code == GIMPLE_ASSIGN && has_undefined_operand)
790	{
791	switch (gimple_assign_rhs_code (gs: stmt))
792	{
793	/* Unary operators are handled with all_undefined_operands. */
794	case PLUS_EXPR:
795	case MINUS_EXPR:
796	case POINTER_PLUS_EXPR:
797	case BIT_XOR_EXPR:
798	/* Not MIN_EXPR, MAX_EXPR. One VARYING operand may be selected.
799	Not bitwise operators, one VARYING operand may specify the
800	result completely.
801	Not logical operators for the same reason, apart from XOR.
802	Not COMPLEX_EXPR as one VARYING operand makes the result partly
803	not UNDEFINED. Not *DIV_EXPR, comparisons and shifts because
804	the undefined operand may be promoted. */
805	return UNDEFINED;
806
807	case ADDR_EXPR:
808	/* If any part of an address is UNDEFINED, like the index
809	of an ARRAY_EXPR, then treat the result as UNDEFINED. */
810	return UNDEFINED;
811
812	default:
813	;
814	}
815	}
816	/* If there was an UNDEFINED operand but the result may be not UNDEFINED
817	fall back to CONSTANT. During iteration UNDEFINED may still drop
818	to CONSTANT. */
819	if (has_undefined_operand)
820	return CONSTANT;
821
822	/* We do not consider virtual operands here -- load from read-only
823	memory may have only VARYING virtual operands, but still be
824	constant. Also we can combine the stmt with definitions from
825	operands whose definitions are not simulated again. */
826	if (has_constant_operand
827	|| has_nsa_operand
828	|| gimple_references_memory_p (stmt))
829	return CONSTANT;
830
831	return VARYING;
832	}
833
834	/* Returns true if STMT cannot be constant. */
835
836	static bool
837	surely_varying_stmt_p (gimple *stmt)
838	{
839	/* If the statement has operands that we cannot handle, it cannot be
840	constant. */
841	if (gimple_has_volatile_ops (stmt))
842	return true;
843
844	/* If it is a call and does not return a value or is not a
845	builtin and not an indirect call or a call to function with
846	assume_aligned/alloc_align attribute, it is varying. */
847	if (is_gimple_call (gs: stmt))
848	{
849	tree fndecl, fntype = gimple_call_fntype (gs: stmt);
850	if (!gimple_call_lhs (gs: stmt)
851	|| ((fndecl = gimple_call_fndecl (gs: stmt)) != NULL_TREE
852	&& !fndecl_built_in_p (node: fndecl)
853	&& !lookup_attribute (attr_name: "assume_aligned",
854	TYPE_ATTRIBUTES (fntype))
855	&& !lookup_attribute (attr_name: "alloc_align",
856	TYPE_ATTRIBUTES (fntype))))
857	return true;
858	}
859
860	/* Any other store operation is not interesting. */
861	else if (gimple_vdef (g: stmt))
862	return true;
863
864	/* Anything other than assignments and conditional jumps are not
865	interesting for CCP. */
866	if (gimple_code (g: stmt) != GIMPLE_ASSIGN
867	&& gimple_code (g: stmt) != GIMPLE_COND
868	&& gimple_code (g: stmt) != GIMPLE_SWITCH
869	&& gimple_code (g: stmt) != GIMPLE_CALL)
870	return true;
871
872	return false;
873	}
874
875	/* Initialize local data structures for CCP. */
876
877	static void
878	ccp_initialize (void)
879	{
880	basic_block bb;
881
882	n_const_val = num_ssa_names;
883	const_val = XCNEWVEC (ccp_prop_value_t, n_const_val);
884
885	/* Initialize simulation flags for PHI nodes and statements. */
886	FOR_EACH_BB_FN (bb, cfun)
887	{
888	gimple_stmt_iterator i;
889
890	for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (i: &i))
891	{
892	gimple *stmt = gsi_stmt (i);
893	bool is_varying;
894
895	/* If the statement is a control insn, then we do not
896	want to avoid simulating the statement once. Failure
897	to do so means that those edges will never get added. */
898	if (stmt_ends_bb_p (stmt))
899	is_varying = false;
900	else
901	is_varying = surely_varying_stmt_p (stmt);
902
903	if (is_varying)
904	{
905	tree def;
906	ssa_op_iter iter;
907
908	/* If the statement will not produce a constant, mark
909	all its outputs VARYING. */
910	FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
911	set_value_varying (def);
912	}
913	prop_set_simulate_again (s: stmt, visit_p: !is_varying);
914	}
915	}
916
917	/* Now process PHI nodes. We never clear the simulate_again flag on
918	phi nodes, since we do not know which edges are executable yet,
919	except for phi nodes for virtual operands when we do not do store ccp. */
920	FOR_EACH_BB_FN (bb, cfun)
921	{
922	gphi_iterator i;
923
924	for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (i: &i))
925	{
926	gphi *phi = i.phi ();
927
928	if (virtual_operand_p (op: gimple_phi_result (gs: phi)))
929	prop_set_simulate_again (s: phi, visit_p: false);
930	else
931	prop_set_simulate_again (s: phi, visit_p: true);
932	}
933	}
934	}
935
936	/* Debug count support. Reset the values of ssa names
937	VARYING when the total number ssa names analyzed is
938	beyond the debug count specified. */
939
940	static void
941	do_dbg_cnt (void)
942	{
943	unsigned i;
944	for (i = 0; i < num_ssa_names; i++)
945	{
946	if (!dbg_cnt (index: ccp))
947	{
948	const_val[i].lattice_val = VARYING;
949	const_val[i].mask = -1;
950	const_val[i].value = NULL_TREE;
951	}
952	}
953	}
954
955
956	/* We want to provide our own GET_VALUE and FOLD_STMT virtual methods. */
957	class ccp_folder : public substitute_and_fold_engine
958	{
959	public:
960	tree value_of_expr (tree, gimple *) final override;
961	bool fold_stmt (gimple_stmt_iterator *) final override;
962	};
963
964	/* This method just wraps GET_CONSTANT_VALUE for now. Over time
965	naked calls to GET_CONSTANT_VALUE should be eliminated in favor
966	of calling member functions. */
967
968	tree
969	ccp_folder::value_of_expr (tree op, gimple *)
970	{
971	return get_constant_value (var: op);
972	}
973
974	/* Do final substitution of propagated values, cleanup the flowgraph and
975	free allocated storage. If NONZERO_P, record nonzero bits.
976
977	Return TRUE when something was optimized. */
978
979	static bool
980	ccp_finalize (bool nonzero_p)
981	{
982	bool something_changed;
983	unsigned i;
984	tree name;
985
986	do_dbg_cnt ();
987
988	/* Derive alignment and misalignment information from partially
989	constant pointers in the lattice or nonzero bits from partially
990	constant integers. */
991	FOR_EACH_SSA_NAME (i, name, cfun)
992	{
993	ccp_prop_value_t *val;
994	unsigned int tem, align;
995
996	if (!POINTER_TYPE_P (TREE_TYPE (name))
997	&& (!INTEGRAL_TYPE_P (TREE_TYPE (name))
998	/* Don't record nonzero bits before IPA to avoid
999	using too much memory. */
1000	|| !nonzero_p))
1001	continue;
1002
1003	val = get_value (var: name);
1004	if (val->lattice_val != CONSTANT
1005	|| TREE_CODE (val->value) != INTEGER_CST
1006	|| val->mask == 0)
1007	continue;
1008
1009	if (POINTER_TYPE_P (TREE_TYPE (name)))
1010	{
1011	/* Trailing mask bits specify the alignment, trailing value
1012	bits the misalignment. */
1013	tem = val->mask.to_uhwi ();
1014	align = least_bit_hwi (x: tem);
1015	if (align > 1)
1016	set_ptr_info_alignment (get_ptr_info (name), align,
1017	(TREE_INT_CST_LOW (val->value)
1018	& (align - 1)));
1019	}
1020	else
1021	{
1022	unsigned int precision = TYPE_PRECISION (TREE_TYPE (val->value));
1023	wide_int value = wi::to_wide (t: val->value);
1024	wide_int mask = wide_int::from (x: val->mask, precision, sgn: UNSIGNED);
1025	set_bitmask (name, value, mask);
1026	}
1027	}
1028
1029	/* Perform substitutions based on the known constant values. */
1030	class ccp_folder ccp_folder;
1031	something_changed = ccp_folder.substitute_and_fold ();
1032
1033	free (ptr: const_val);
1034	const_val = NULL;
1035	return something_changed;
1036	}
1037
1038
1039	/* Compute the meet operator between *VAL1 and *VAL2. Store the result
1040	in VAL1.
1041
1042	any M UNDEFINED = any
1043	any M VARYING = VARYING
1044	Ci M Cj = Ci if (i == j)
1045	Ci M Cj = VARYING if (i != j)
1046	*/
1047
1048	static void
1049	ccp_lattice_meet (ccp_prop_value_t *val1, ccp_prop_value_t *val2)
1050	{
1051	if (val1->lattice_val == UNDEFINED
1052	/* For UNDEFINED M SSA we can't always SSA because its definition
1053	may not dominate the PHI node. Doing optimistic copy propagation
1054	also causes a lot of gcc.dg/uninit-pred*.c FAILs. */
1055	&& (val2->lattice_val != CONSTANT
1056	|| TREE_CODE (val2->value) != SSA_NAME))
1057	{
1058	/* UNDEFINED M any = any */
1059	*val1 = *val2;
1060	}
1061	else if (val2->lattice_val == UNDEFINED
1062	/* See above. */
1063	&& (val1->lattice_val != CONSTANT
1064	|| TREE_CODE (val1->value) != SSA_NAME))
1065	{
1066	/* any M UNDEFINED = any
1067	Nothing to do. VAL1 already contains the value we want. */
1068	;
1069	}
1070	else if (val1->lattice_val == VARYING
1071	|| val2->lattice_val == VARYING)
1072	{
1073	/* any M VARYING = VARYING. */
1074	val1->lattice_val = VARYING;
1075	val1->mask = -1;
1076	val1->value = NULL_TREE;
1077	}
1078	else if (val1->lattice_val == CONSTANT
1079	&& val2->lattice_val == CONSTANT
1080	&& TREE_CODE (val1->value) == INTEGER_CST
1081	&& TREE_CODE (val2->value) == INTEGER_CST)
1082	{
1083	/* Ci M Cj = Ci if (i == j)
1084	Ci M Cj = VARYING if (i != j)
1085
1086	For INTEGER_CSTs mask unequal bits. If no equal bits remain,
1087	drop to varying. */
1088	val1->mask = (val1->mask | val2->mask
1089	| (wi::to_widest (t: val1->value)
1090	^ wi::to_widest (t: val2->value)));
1091	if (wi::sext (x: val1->mask, TYPE_PRECISION (TREE_TYPE (val1->value))) == -1)
1092	{
1093	val1->lattice_val = VARYING;
1094	val1->value = NULL_TREE;
1095	}
1096	}
1097	else if (val1->lattice_val == CONSTANT
1098	&& val2->lattice_val == CONSTANT
1099	&& operand_equal_p (val1->value, val2->value, flags: 0))
1100	{
1101	/* Ci M Cj = Ci if (i == j)
1102	Ci M Cj = VARYING if (i != j)
1103
1104	VAL1 already contains the value we want for equivalent values. */
1105	}
1106	else if (val1->lattice_val == CONSTANT
1107	&& val2->lattice_val == CONSTANT
1108	&& (TREE_CODE (val1->value) == ADDR_EXPR
1109	|| TREE_CODE (val2->value) == ADDR_EXPR))
1110	{
1111	/* When not equal addresses are involved try meeting for
1112	alignment. */
1113	ccp_prop_value_t tem = *val2;
1114	if (TREE_CODE (val1->value) == ADDR_EXPR)
1115	*val1 = get_value_for_expr (expr: val1->value, for_bits_p: true);
1116	if (TREE_CODE (val2->value) == ADDR_EXPR)
1117	tem = get_value_for_expr (expr: val2->value, for_bits_p: true);
1118	ccp_lattice_meet (val1, val2: &tem);
1119	}
1120	else
1121	{
1122	/* Any other combination is VARYING. */
1123	val1->lattice_val = VARYING;
1124	val1->mask = -1;
1125	val1->value = NULL_TREE;
1126	}
1127	}
1128
1129
1130	/* Loop through the PHI_NODE's parameters for BLOCK and compare their
1131	lattice values to determine PHI_NODE's lattice value. The value of a
1132	PHI node is determined calling ccp_lattice_meet with all the arguments
1133	of the PHI node that are incoming via executable edges. */
1134
1135	enum ssa_prop_result
1136	ccp_propagate::visit_phi (gphi *phi)
1137	{
1138	unsigned i;
1139	ccp_prop_value_t new_val;
1140
1141	if (dump_file && (dump_flags & TDF_DETAILS))
1142	{
1143	fprintf (stream: dump_file, format: "\nVisiting PHI node: ");
1144	print_gimple_stmt (dump_file, phi, 0, dump_flags);
1145	}
1146
1147	new_val.lattice_val = UNDEFINED;
1148	new_val.value = NULL_TREE;
1149	new_val.mask = 0;
1150
1151	bool first = true;
1152	bool non_exec_edge = false;
1153	for (i = 0; i < gimple_phi_num_args (gs: phi); i++)
1154	{
1155	/* Compute the meet operator over all the PHI arguments flowing
1156	through executable edges. */
1157	edge e = gimple_phi_arg_edge (phi, i);
1158
1159	if (dump_file && (dump_flags & TDF_DETAILS))
1160	{
1161	fprintf (stream: dump_file,
1162	format: "\tArgument #%d (%d -> %d %sexecutable)\n",
1163	i, e->src->index, e->dest->index,
1164	(e->flags & EDGE_EXECUTABLE) ? "" : "not ");
1165	}
1166
1167	/* If the incoming edge is executable, Compute the meet operator for
1168	the existing value of the PHI node and the current PHI argument. */
1169	if (e->flags & EDGE_EXECUTABLE)
1170	{
1171	tree arg = gimple_phi_arg (gs: phi, index: i)->def;
1172	ccp_prop_value_t arg_val = get_value_for_expr (expr: arg, for_bits_p: false);
1173
1174	if (first)
1175	{
1176	new_val = arg_val;
1177	first = false;
1178	}
1179	else
1180	ccp_lattice_meet (val1: &new_val, val2: &arg_val);
1181
1182	if (dump_file && (dump_flags & TDF_DETAILS))
1183	{
1184	fprintf (stream: dump_file, format: "\t");
1185	print_generic_expr (dump_file, arg, dump_flags);
1186	dump_lattice_value (outf: dump_file, prefix: "\tValue: ", val: arg_val);
1187	fprintf (stream: dump_file, format: "\n");
1188	}
1189
1190	if (new_val.lattice_val == VARYING)
1191	break;
1192	}
1193	else
1194	non_exec_edge = true;
1195	}
1196
1197	/* In case there were non-executable edges and the value is a copy
1198	make sure its definition dominates the PHI node. */
1199	if (non_exec_edge
1200	&& new_val.lattice_val == CONSTANT
1201	&& TREE_CODE (new_val.value) == SSA_NAME
1202	&& ! SSA_NAME_IS_DEFAULT_DEF (new_val.value)
1203	&& ! dominated_by_p (CDI_DOMINATORS, gimple_bb (g: phi),
1204	gimple_bb (SSA_NAME_DEF_STMT (new_val.value))))
1205	{
1206	new_val.lattice_val = VARYING;
1207	new_val.value = NULL_TREE;
1208	new_val.mask = -1;
1209	}
1210
1211	if (dump_file && (dump_flags & TDF_DETAILS))
1212	{
1213	dump_lattice_value (outf: dump_file, prefix: "\n PHI node value: ", val: new_val);
1214	fprintf (stream: dump_file, format: "\n\n");
1215	}
1216
1217	/* Make the transition to the new value. */
1218	if (set_lattice_value (var: gimple_phi_result (gs: phi), new_val: &new_val))
1219	{
1220	if (new_val.lattice_val == VARYING)
1221	return SSA_PROP_VARYING;
1222	else
1223	return SSA_PROP_INTERESTING;
1224	}
1225	else
1226	return SSA_PROP_NOT_INTERESTING;
1227	}
1228
1229	/* Return the constant value for OP or OP otherwise. */
1230
1231	static tree
1232	valueize_op (tree op)
1233	{
1234	if (TREE_CODE (op) == SSA_NAME)
1235	{
1236	tree tem = get_constant_value (var: op);
1237	if (tem)
1238	return tem;
1239	}
1240	return op;
1241	}
1242
1243	/* Return the constant value for OP, but signal to not follow SSA
1244	edges if the definition may be simulated again. */
1245
1246	static tree
1247	valueize_op_1 (tree op)
1248	{
1249	if (TREE_CODE (op) == SSA_NAME)
1250	{
1251	/* If the definition may be simulated again we cannot follow
1252	this SSA edge as the SSA propagator does not necessarily
1253	re-visit the use. */
1254	gimple *def_stmt = SSA_NAME_DEF_STMT (op);
1255	if (!gimple_nop_p (g: def_stmt)
1256	&& prop_simulate_again_p (s: def_stmt))
1257	return NULL_TREE;
1258	tree tem = get_constant_value (var: op);
1259	if (tem)
1260	return tem;
1261	}
1262	return op;
1263	}
1264
1265	/* CCP specific front-end to the non-destructive constant folding
1266	routines.
1267
1268	Attempt to simplify the RHS of STMT knowing that one or more
1269	operands are constants.
1270
1271	If simplification is possible, return the simplified RHS,
1272	otherwise return the original RHS or NULL_TREE. */
1273
1274	static tree
1275	ccp_fold (gimple *stmt)
1276	{
1277	switch (gimple_code (g: stmt))
1278	{
1279	case GIMPLE_SWITCH:
1280	{
1281	/* Return the constant switch index. */
1282	return valueize_op (op: gimple_switch_index (gs: as_a <gswitch *> (p: stmt)));
1283	}
1284
1285	case GIMPLE_COND:
1286	case GIMPLE_ASSIGN:
1287	case GIMPLE_CALL:
1288	return gimple_fold_stmt_to_constant_1 (stmt,
1289	valueize_op, valueize_op_1);
1290
1291	default:
1292	gcc_unreachable ();
1293	}
1294	}
1295
1296	/* Determine the minimum and maximum values, *MIN and *MAX respectively,
1297	represented by the mask pair VAL and MASK with signedness SGN and
1298	precision PRECISION. */
1299
1300	static void
1301	value_mask_to_min_max (widest_int *min, widest_int *max,
1302	const widest_int &val, const widest_int &mask,
1303	signop sgn, int precision)
1304	{
1305	*min = wi::bit_and_not (x: val, y: mask);
1306	*max = val | mask;
1307	if (sgn == SIGNED && wi::neg_p (x: mask))
1308	{
1309	widest_int sign_bit = wi::lshift (x: 1, y: precision - 1);
1310	*min ^= sign_bit;
1311	*max ^= sign_bit;
1312	/* MAX is zero extended, and MIN is sign extended. */
1313	*min = wi::ext (x: *min, offset: precision, sgn);
1314	*max = wi::ext (x: *max, offset: precision, sgn);
1315	}
1316	}
1317
1318	/* Apply the operation CODE in type TYPE to the value, mask pair
1319	RVAL and RMASK representing a value of type RTYPE and set
1320	the value, mask pair *VAL and *MASK to the result. */
1321
1322	void
1323	bit_value_unop (enum tree_code code, signop type_sgn, int type_precision,
1324	widest_int *val, widest_int *mask,
1325	signop rtype_sgn, int rtype_precision,
1326	const widest_int &rval, const widest_int &rmask)
1327	{
1328	switch (code)
1329	{
1330	case BIT_NOT_EXPR:
1331	*mask = rmask;
1332	*val = ~rval;
1333	break;
1334
1335	case NEGATE_EXPR:
1336	{
1337	widest_int temv, temm;
1338	/* Return ~rval + 1. */
1339	bit_value_unop (code: BIT_NOT_EXPR, type_sgn, type_precision, val: &temv, mask: &temm,
1340	rtype_sgn: type_sgn, rtype_precision: type_precision, rval, rmask);
1341	bit_value_binop (PLUS_EXPR, type_sgn, type_precision, val, mask,
1342	type_sgn, type_precision, temv, temm,
1343	type_sgn, type_precision, 1, 0);
1344	break;
1345	}
1346
1347	CASE_CONVERT:
1348	{
1349	/* First extend mask and value according to the original type. */
1350	*mask = wi::ext (x: rmask, offset: rtype_precision, sgn: rtype_sgn);
1351	*val = wi::ext (x: rval, offset: rtype_precision, sgn: rtype_sgn);
1352
1353	/* Then extend mask and value according to the target type. */
1354	*mask = wi::ext (x: *mask, offset: type_precision, sgn: type_sgn);
1355	*val = wi::ext (x: *val, offset: type_precision, sgn: type_sgn);
1356	break;
1357	}
1358
1359	case ABS_EXPR:
1360	case ABSU_EXPR:
1361	if (wi::sext (x: rmask, offset: rtype_precision) == -1)
1362	{
1363	*mask = -1;
1364	*val = 0;
1365	}
1366	else if (wi::neg_p (x: rmask))
1367	{
1368	/* Result is either rval or -rval. */
1369	widest_int temv, temm;
1370	bit_value_unop (code: NEGATE_EXPR, type_sgn: rtype_sgn, type_precision: rtype_precision, val: &temv,
1371	mask: &temm, rtype_sgn: type_sgn, rtype_precision: type_precision, rval, rmask);
1372	temm |= (rmask | (rval ^ temv));
1373	/* Extend the result. */
1374	*mask = wi::ext (x: temm, offset: type_precision, sgn: type_sgn);
1375	*val = wi::ext (x: temv, offset: type_precision, sgn: type_sgn);
1376	}
1377	else if (wi::neg_p (x: rval))
1378	{
1379	bit_value_unop (code: NEGATE_EXPR, type_sgn, type_precision, val, mask,
1380	rtype_sgn: type_sgn, rtype_precision: type_precision, rval, rmask);
1381	}
1382	else
1383	{
1384	*mask = rmask;
1385	*val = rval;
1386	}
1387	break;
1388
1389	default:
1390	*mask = -1;
1391	*val = 0;
1392	break;
1393	}
1394	}
1395
1396	/* Determine the mask pair *VAL and *MASK from multiplying the
1397	argument mask pair RVAL, RMASK by the unsigned constant C. */
1398	static void
1399	bit_value_mult_const (signop sgn, int width,
1400	widest_int *val, widest_int *mask,
1401	const widest_int &rval, const widest_int &rmask,
1402	widest_int c)
1403	{
1404	widest_int sum_mask = 0;
1405
1406	/* Ensure rval_lo only contains known bits. */
1407	widest_int rval_lo = wi::bit_and_not (x: rval, y: rmask);
1408
1409	if (rval_lo != 0)
1410	{
1411	/* General case (some bits of multiplicand are known set). */
1412	widest_int sum_val = 0;
1413	while (c != 0)
1414	{
1415	/* Determine the lowest bit set in the multiplier. */
1416	int bitpos = wi::ctz (c);
1417	widest_int term_mask = rmask << bitpos;
1418	widest_int term_val = rval_lo << bitpos;
1419
1420	/* sum += term. */
1421	widest_int lo = sum_val + term_val;
1422	widest_int hi = (sum_val | sum_mask) + (term_val | term_mask);
1423	sum_mask |= term_mask | (lo ^ hi);
1424	sum_val = lo;
1425
1426	/* Clear this bit in the multiplier. */
1427	c ^= wi::lshift (x: 1, y: bitpos);
1428	}
1429	/* Correctly extend the result value. */
1430	*val = wi::ext (x: sum_val, offset: width, sgn);
1431	}
1432	else
1433	{
1434	/* Special case (no bits of multiplicand are known set). */
1435	while (c != 0)
1436	{
1437	/* Determine the lowest bit set in the multiplier. */
1438	int bitpos = wi::ctz (c);
1439	widest_int term_mask = rmask << bitpos;
1440
1441	/* sum += term. */
1442	widest_int hi = sum_mask + term_mask;
1443	sum_mask |= term_mask | hi;
1444
1445	/* Clear this bit in the multiplier. */
1446	c ^= wi::lshift (x: 1, y: bitpos);
1447	}
1448	*val = 0;
1449	}
1450
1451	/* Correctly extend the result mask. */
1452	*mask = wi::ext (x: sum_mask, offset: width, sgn);
1453	}
1454
1455	/* Fill up to MAX values in the BITS array with values representing
1456	each of the non-zero bits in the value X. Returns the number of
1457	bits in X (capped at the maximum value MAX). For example, an X
1458	value 11, places 1, 2 and 8 in BITS and returns the value 3. */
1459
1460	static unsigned int
1461	get_individual_bits (widest_int *bits, widest_int x, unsigned int max)
1462	{
1463	unsigned int count = 0;
1464	while (count < max && x != 0)
1465	{
1466	int bitpos = wi::ctz (x);
1467	bits[count] = wi::lshift (x: 1, y: bitpos);
1468	x ^= bits[count];
1469	count++;
1470	}
1471	return count;
1472	}
1473
1474	/* Array of 2^N - 1 values representing the bits flipped between
1475	consecutive Gray codes. This is used to efficiently enumerate
1476	all permutations on N bits using XOR. */
1477	static const unsigned char gray_code_bit_flips[63] = {
1478	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
1479	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
1480	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
1481	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
1482	};
1483
1484	/* Apply the operation CODE in type TYPE to the value, mask pairs
1485	R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE
1486	and R2TYPE and set the value, mask pair *VAL and *MASK to the result. */
1487
1488	void
1489	bit_value_binop (enum tree_code code, signop sgn, int width,
1490	widest_int *val, widest_int *mask,
1491	signop r1type_sgn, int r1type_precision,
1492	const widest_int &r1val, const widest_int &r1mask,
1493	signop r2type_sgn, int r2type_precision ATTRIBUTE_UNUSED,
1494	const widest_int &r2val, const widest_int &r2mask)
1495	{
1496	bool swap_p = false;
1497
1498	/* Assume we'll get a constant result. Use an initial non varying
1499	value, we fall back to varying in the end if necessary. */
1500	*mask = -1;
1501	/* Ensure that VAL is initialized (to any value). */
1502	*val = 0;
1503
1504	switch (code)
1505	{
1506	case BIT_AND_EXPR:
1507	/* The mask is constant where there is a known not
1508	set bit, (m1 | m2) & ((v1 | m1) & (v2 | m2)) */
1509	*mask = (r1mask | r2mask) & (r1val | r1mask) & (r2val | r2mask);
1510	*val = r1val & r2val;
1511	break;
1512
1513	case BIT_IOR_EXPR:
1514	/* The mask is constant where there is a known
1515	set bit, (m1 | m2) & ~((v1 & ~m1) | (v2 & ~m2)). */
1516	*mask = wi::bit_and_not (x: r1mask | r2mask,
1517	y: wi::bit_and_not (x: r1val, y: r1mask)
1518	| wi::bit_and_not (x: r2val, y: r2mask));
1519	*val = r1val | r2val;
1520	break;
1521
1522	case BIT_XOR_EXPR:
1523	/* m1 | m2 */
1524	*mask = r1mask | r2mask;
1525	*val = r1val ^ r2val;
1526	break;
1527
1528	case LROTATE_EXPR:
1529	case RROTATE_EXPR:
1530	if (r2mask == 0)
1531	{
1532	widest_int shift = r2val;
1533	if (shift == 0)
1534	{
1535	*mask = r1mask;
1536	*val = r1val;
1537	}
1538	else
1539	{
1540	if (wi::neg_p (x: shift, sgn: r2type_sgn))
1541	{
1542	shift = -shift;
1543	if (code == RROTATE_EXPR)
1544	code = LROTATE_EXPR;
1545	else
1546	code = RROTATE_EXPR;
1547	}
1548	if (code == RROTATE_EXPR)
1549	{
1550	*mask = wi::rrotate (x: r1mask, y: shift, width);
1551	*val = wi::rrotate (x: r1val, y: shift, width);
1552	}
1553	else
1554	{
1555	*mask = wi::lrotate (x: r1mask, y: shift, width);
1556	*val = wi::lrotate (x: r1val, y: shift, width);
1557	}
1558	*mask = wi::ext (x: *mask, offset: width, sgn);
1559	*val = wi::ext (x: *val, offset: width, sgn);
1560	}
1561	}
1562	else if (wi::ltu_p (x: r2val | r2mask, y: width)
1563	&& wi::popcount (r2mask) <= 4)
1564	{
1565	widest_int bits[4];
1566	widest_int res_val, res_mask;
1567	widest_int tmp_val, tmp_mask;
1568	widest_int shift = wi::bit_and_not (x: r2val, y: r2mask);
1569	unsigned int bit_count = get_individual_bits (bits, x: r2mask, max: 4);
1570	unsigned int count = (1 << bit_count) - 1;
1571
1572	/* Initialize result to rotate by smallest value of shift. */
1573	if (code == RROTATE_EXPR)
1574	{
1575	res_mask = wi::rrotate (x: r1mask, y: shift, width);
1576	res_val = wi::rrotate (x: r1val, y: shift, width);
1577	}
1578	else
1579	{
1580	res_mask = wi::lrotate (x: r1mask, y: shift, width);
1581	res_val = wi::lrotate (x: r1val, y: shift, width);
1582	}
1583
1584	/* Iterate through the remaining values of shift. */
1585	for (unsigned int i=0; i<count; i++)
1586	{
1587	shift ^= bits[gray_code_bit_flips[i]];
1588	if (code == RROTATE_EXPR)
1589	{
1590	tmp_mask = wi::rrotate (x: r1mask, y: shift, width);
1591	tmp_val = wi::rrotate (x: r1val, y: shift, width);
1592	}
1593	else
1594	{
1595	tmp_mask = wi::lrotate (x: r1mask, y: shift, width);
1596	tmp_val = wi::lrotate (x: r1val, y: shift, width);
1597	}
1598	/* Accumulate the result. */
1599	res_mask |= tmp_mask | (res_val ^ tmp_val);
1600	}
1601	*val = wi::ext (x: wi::bit_and_not (x: res_val, y: res_mask), offset: width, sgn);
1602	*mask = wi::ext (x: res_mask, offset: width, sgn);
1603	}
1604	break;
1605
1606	case LSHIFT_EXPR:
1607	case RSHIFT_EXPR:
1608	/* ??? We can handle partially known shift counts if we know
1609	its sign. That way we can tell that (x << (y | 8)) & 255
1610	is zero. */
1611	if (r2mask == 0)
1612	{
1613	widest_int shift = r2val;
1614	if (shift == 0)
1615	{
1616	*mask = r1mask;
1617	*val = r1val;
1618	}
1619	else
1620	{
1621	if (wi::neg_p (x: shift, sgn: r2type_sgn))
1622	break;
1623	if (code == RSHIFT_EXPR)
1624	{
1625	*mask = wi::rshift (x: wi::ext (x: r1mask, offset: width, sgn), y: shift, sgn);
1626	*val = wi::rshift (x: wi::ext (x: r1val, offset: width, sgn), y: shift, sgn);
1627	}
1628	else
1629	{
1630	*mask = wi::ext (x: r1mask << shift, offset: width, sgn);
1631	*val = wi::ext (x: r1val << shift, offset: width, sgn);
1632	}
1633	}
1634	}
1635	else if (wi::ltu_p (x: r2val | r2mask, y: width))
1636	{
1637	if (wi::popcount (r2mask) <= 4)
1638	{
1639	widest_int bits[4];
1640	widest_int arg_val, arg_mask;
1641	widest_int res_val, res_mask;
1642	widest_int tmp_val, tmp_mask;
1643	widest_int shift = wi::bit_and_not (x: r2val, y: r2mask);
1644	unsigned int bit_count = get_individual_bits (bits, x: r2mask, max: 4);
1645	unsigned int count = (1 << bit_count) - 1;
1646
1647	/* Initialize result to shift by smallest value of shift. */
1648	if (code == RSHIFT_EXPR)
1649	{
1650	arg_mask = wi::ext (x: r1mask, offset: width, sgn);
1651	arg_val = wi::ext (x: r1val, offset: width, sgn);
1652	res_mask = wi::rshift (x: arg_mask, y: shift, sgn);
1653	res_val = wi::rshift (x: arg_val, y: shift, sgn);
1654	}
1655	else
1656	{
1657	arg_mask = r1mask;
1658	arg_val = r1val;
1659	res_mask = arg_mask << shift;
1660	res_val = arg_val << shift;
1661	}
1662
1663	/* Iterate through the remaining values of shift. */
1664	for (unsigned int i=0; i<count; i++)
1665	{
1666	shift ^= bits[gray_code_bit_flips[i]];
1667	if (code == RSHIFT_EXPR)
1668	{
1669	tmp_mask = wi::rshift (x: arg_mask, y: shift, sgn);
1670	tmp_val = wi::rshift (x: arg_val, y: shift, sgn);
1671	}
1672	else
1673	{
1674	tmp_mask = arg_mask << shift;
1675	tmp_val = arg_val << shift;
1676	}
1677	/* Accumulate the result. */
1678	res_mask |= tmp_mask | (res_val ^ tmp_val);
1679	}
1680	res_mask = wi::ext (x: res_mask, offset: width, sgn);
1681	res_val = wi::ext (x: res_val, offset: width, sgn);
1682	*val = wi::bit_and_not (x: res_val, y: res_mask);
1683	*mask = res_mask;
1684	}
1685	else if ((r1val | r1mask) == 0)
1686	{
1687	/* Handle shifts of zero to avoid undefined wi::ctz below. */
1688	*mask = 0;
1689	*val = 0;
1690	}
1691	else if (code == LSHIFT_EXPR)
1692	{
1693	widest_int tmp = wi::mask <widest_int> (width, negate_p: false);
1694	tmp <<= wi::ctz (r1val | r1mask);
1695	tmp <<= wi::bit_and_not (x: r2val, y: r2mask);
1696	*mask = wi::ext (x: tmp, offset: width, sgn);
1697	*val = 0;
1698	}
1699	else if (!wi::neg_p (x: r1val | r1mask, sgn))
1700	{
1701	/* Logical right shift, or zero sign bit. */
1702	widest_int arg = r1val | r1mask;
1703	int lzcount = wi::clz (arg);
1704	if (lzcount)
1705	lzcount -= wi::get_precision (x: arg) - width;
1706	widest_int tmp = wi::mask <widest_int> (width, negate_p: false);
1707	tmp = wi::lrshift (x: tmp, y: lzcount);
1708	tmp = wi::lrshift (x: tmp, y: wi::bit_and_not (x: r2val, y: r2mask));
1709	*mask = wi::ext (x: tmp, offset: width, sgn);
1710	*val = 0;
1711	}
1712	else if (!wi::neg_p (x: r1mask))
1713	{
1714	/* Arithmetic right shift with set sign bit. */
1715	widest_int arg = wi::bit_and_not (x: r1val, y: r1mask);
1716	int sbcount = wi::clrsb (arg);
1717	sbcount -= wi::get_precision (x: arg) - width;
1718	widest_int tmp = wi::mask <widest_int> (width, negate_p: false);
1719	tmp = wi::lrshift (x: tmp, y: sbcount);
1720	tmp = wi::lrshift (x: tmp, y: wi::bit_and_not (x: r2val, y: r2mask));
1721	*mask = wi::sext (x: tmp, offset: width);
1722	tmp = wi::bit_not (x: tmp);
1723	*val = wi::sext (x: tmp, offset: width);
1724	}
1725	}
1726	break;
1727
1728	case PLUS_EXPR:
1729	case POINTER_PLUS_EXPR:
1730	{
1731	/* Do the addition with unknown bits set to zero, to give carry-ins of
1732	zero wherever possible. */
1733	widest_int lo = (wi::bit_and_not (x: r1val, y: r1mask)
1734	+ wi::bit_and_not (x: r2val, y: r2mask));
1735	lo = wi::ext (x: lo, offset: width, sgn);
1736	/* Do the addition with unknown bits set to one, to give carry-ins of
1737	one wherever possible. */
1738	widest_int hi = (r1val | r1mask) + (r2val | r2mask);
1739	hi = wi::ext (x: hi, offset: width, sgn);
1740	/* Each bit in the result is known if (a) the corresponding bits in
1741	both inputs are known, and (b) the carry-in to that bit position
1742	is known. We can check condition (b) by seeing if we got the same
1743	result with minimised carries as with maximised carries. */
1744	*mask = r1mask | r2mask | (lo ^ hi);
1745	*mask = wi::ext (x: *mask, offset: width, sgn);
1746	/* It shouldn't matter whether we choose lo or hi here. */
1747	*val = lo;
1748	break;
1749	}
1750
1751	case MINUS_EXPR:
1752	case POINTER_DIFF_EXPR:
1753	{
1754	/* Subtraction is derived from the addition algorithm above. */
1755	widest_int lo = wi::bit_and_not (x: r1val, y: r1mask) - (r2val | r2mask);
1756	lo = wi::ext (x: lo, offset: width, sgn);
1757	widest_int hi = (r1val | r1mask) - wi::bit_and_not (x: r2val, y: r2mask);
1758	hi = wi::ext (x: hi, offset: width, sgn);
1759	*mask = r1mask | r2mask | (lo ^ hi);
1760	*mask = wi::ext (x: *mask, offset: width, sgn);
1761	*val = lo;
1762	break;
1763	}
1764
1765	case MULT_EXPR:
1766	if (r2mask == 0
1767	&& !wi::neg_p (x: r2val, sgn)
1768	&& (flag_expensive_optimizations || wi::popcount (r2val) < 8))
1769	bit_value_mult_const (sgn, width, val, mask, rval: r1val, rmask: r1mask, c: r2val);
1770	else if (r1mask == 0
1771	&& !wi::neg_p (x: r1val, sgn)
1772	&& (flag_expensive_optimizations || wi::popcount (r1val) < 8))
1773	bit_value_mult_const (sgn, width, val, mask, rval: r2val, rmask: r2mask, c: r1val);
1774	else
1775	{
1776	/* Just track trailing zeros in both operands and transfer
1777	them to the other. */
1778	int r1tz = wi::ctz (r1val | r1mask);
1779	int r2tz = wi::ctz (r2val | r2mask);
1780	if (r1tz + r2tz >= width)
1781	{
1782	*mask = 0;
1783	*val = 0;
1784	}
1785	else if (r1tz + r2tz > 0)
1786	{
1787	*mask = wi::ext (x: wi::mask <widest_int> (width: r1tz + r2tz, negate_p: true),
1788	offset: width, sgn);
1789	*val = 0;
1790	}
1791	}
1792	break;
1793
1794	case EQ_EXPR:
1795	case NE_EXPR:
1796	{
1797	widest_int m = r1mask | r2mask;
1798	if (wi::bit_and_not (x: r1val, y: m) != wi::bit_and_not (x: r2val, y: m))
1799	{
1800	*mask = 0;
1801	*val = ((code == EQ_EXPR) ? 0 : 1);
1802	}
1803	else
1804	{
1805	/* We know the result of a comparison is always one or zero. */
1806	*mask = 1;
1807	*val = 0;
1808	}
1809	break;
1810	}
1811
1812	case GE_EXPR:
1813	case GT_EXPR:
1814	swap_p = true;
1815	code = swap_tree_comparison (code);
1816	/* Fall through. */
1817	case LT_EXPR:
1818	case LE_EXPR:
1819	{
1820	widest_int min1, max1, min2, max2;
1821	int minmax, maxmin;
1822
1823	const widest_int &o1val = swap_p ? r2val : r1val;
1824	const widest_int &o1mask = swap_p ? r2mask : r1mask;
1825	const widest_int &o2val = swap_p ? r1val : r2val;
1826	const widest_int &o2mask = swap_p ? r1mask : r2mask;
1827
1828	value_mask_to_min_max (min: &min1, max: &max1, val: o1val, mask: o1mask,
1829	sgn: r1type_sgn, precision: r1type_precision);
1830	value_mask_to_min_max (min: &min2, max: &max2, val: o2val, mask: o2mask,
1831	sgn: r1type_sgn, precision: r1type_precision);
1832
1833	/* For comparisons the signedness is in the comparison operands. */
1834	/* Do a cross comparison of the max/min pairs. */
1835	maxmin = wi::cmp (x: max1, y: min2, sgn: r1type_sgn);
1836	minmax = wi::cmp (x: min1, y: max2, sgn: r1type_sgn);
1837	if (maxmin < (code == LE_EXPR ? 1: 0)) /* o1 < or <= o2. */
1838	{
1839	*mask = 0;
1840	*val = 1;
1841	}
1842	else if (minmax > (code == LT_EXPR ? -1 : 0)) /* o1 >= or > o2. */
1843	{
1844	*mask = 0;
1845	*val = 0;
1846	}
1847	else if (maxmin == minmax) /* o1 and o2 are equal. */
1848	{
1849	/* This probably should never happen as we'd have
1850	folded the thing during fully constant value folding. */
1851	*mask = 0;
1852	*val = (code == LE_EXPR ? 1 : 0);
1853	}
1854	else
1855	{
1856	/* We know the result of a comparison is always one or zero. */
1857	*mask = 1;
1858	*val = 0;
1859	}
1860	break;
1861	}
1862
1863	case MIN_EXPR:
1864	case MAX_EXPR:
1865	{
1866	widest_int min1, max1, min2, max2;
1867
1868	value_mask_to_min_max (min: &min1, max: &max1, val: r1val, mask: r1mask, sgn, precision: width);
1869	value_mask_to_min_max (min: &min2, max: &max2, val: r2val, mask: r2mask, sgn, precision: width);
1870
1871	if (wi::cmp (x: max1, y: min2, sgn) <= 0) /* r1 is less than r2. */
1872	{
1873	if (code == MIN_EXPR)
1874	{
1875	*mask = r1mask;
1876	*val = r1val;
1877	}
1878	else
1879	{
1880	*mask = r2mask;
1881	*val = r2val;
1882	}
1883	}
1884	else if (wi::cmp (x: min1, y: max2, sgn) >= 0) /* r2 is less than r1. */
1885	{
1886	if (code == MIN_EXPR)
1887	{
1888	*mask = r2mask;
1889	*val = r2val;
1890	}
1891	else
1892	{
1893	*mask = r1mask;
1894	*val = r1val;
1895	}
1896	}
1897	else
1898	{
1899	/* The result is either r1 or r2. */
1900	*mask = r1mask | r2mask | (r1val ^ r2val);
1901	*val = r1val;
1902	}
1903	break;
1904	}
1905
1906	case TRUNC_MOD_EXPR:
1907	{
1908	widest_int r1max = r1val | r1mask;
1909	widest_int r2max = r2val | r2mask;
1910	if (sgn == UNSIGNED
1911	|| (!wi::neg_p (x: r1max) && !wi::neg_p (x: r2max)))
1912	{
1913	/* Confirm R2 has some bits set, to avoid division by zero. */
1914	widest_int r2min = wi::bit_and_not (x: r2val, y: r2mask);
1915	if (r2min != 0)
1916	{
1917	/* R1 % R2 is R1 if R1 is always less than R2. */
1918	if (wi::ltu_p (x: r1max, y: r2min))
1919	{
1920	*mask = r1mask;
1921	*val = r1val;
1922	}
1923	else
1924	{
1925	/* R1 % R2 is always less than the maximum of R2. */
1926	unsigned int lzcount = wi::clz (r2max);
1927	unsigned int bits = wi::get_precision (x: r2max) - lzcount;
1928	if (r2max == wi::lshift (x: 1, y: bits))
1929	bits--;
1930	*mask = wi::mask <widest_int> (width: bits, negate_p: false);
1931	*val = 0;
1932	}
1933	}
1934	}
1935	}
1936	break;
1937
1938	case TRUNC_DIV_EXPR:
1939	{
1940	widest_int r1max = r1val | r1mask;
1941	widest_int r2max = r2val | r2mask;
1942	if (r2mask == 0 && !wi::neg_p (x: r1max))
1943	{
1944	widest_int shift = wi::exact_log2 (r2val);
1945	if (shift != -1)
1946	{
1947	// Handle division by a power of 2 as an rshift.
1948	bit_value_binop (code: RSHIFT_EXPR, sgn, width, val, mask,
1949	r1type_sgn, r1type_precision, r1val, r1mask,
1950	r2type_sgn, r2type_precision, r2val: shift, r2mask);
1951	return;
1952	}
1953	}
1954	if (sgn == UNSIGNED
1955	|| (!wi::neg_p (x: r1max) && !wi::neg_p (x: r2max)))
1956	{
1957	/* Confirm R2 has some bits set, to avoid division by zero. */
1958	widest_int r2min = wi::bit_and_not (x: r2val, y: r2mask);
1959	if (r2min != 0)
1960	{
1961	/* R1 / R2 is zero if R1 is always less than R2. */
1962	if (wi::ltu_p (x: r1max, y: r2min))
1963	{
1964	*mask = 0;
1965	*val = 0;
1966	}
1967	else
1968	{
1969	widest_int upper
1970	= wi::udiv_trunc (x: wi::zext (x: r1max, offset: width), y: r2min);
1971	unsigned int lzcount = wi::clz (upper);
1972	unsigned int bits = wi::get_precision (x: upper) - lzcount;
1973	*mask = wi::mask <widest_int> (width: bits, negate_p: false);
1974	*val = 0;
1975	}
1976	}
1977	}
1978	}
1979	break;
1980
1981	default:;
1982	}
1983	}
1984
1985	/* Return the propagation value when applying the operation CODE to
1986	the value RHS yielding type TYPE. */
1987
1988	static ccp_prop_value_t
1989	bit_value_unop (enum tree_code code, tree type, tree rhs)
1990	{
1991	ccp_prop_value_t rval = get_value_for_expr (expr: rhs, for_bits_p: true);
1992	widest_int value, mask;
1993	ccp_prop_value_t val;
1994
1995	if (rval.lattice_val == UNDEFINED)
1996	return rval;
1997
1998	gcc_assert ((rval.lattice_val == CONSTANT
1999	&& TREE_CODE (rval.value) == INTEGER_CST)
2000	|| wi::sext (rval.mask, TYPE_PRECISION (TREE_TYPE (rhs))) == -1);
2001	bit_value_unop (code, TYPE_SIGN (type), TYPE_PRECISION (type), val: &value, mask: &mask,
2002	TYPE_SIGN (TREE_TYPE (rhs)), TYPE_PRECISION (TREE_TYPE (rhs)),
2003	rval: value_to_wide_int (val: rval), rmask: rval.mask);
2004	if (wi::sext (x: mask, TYPE_PRECISION (type)) != -1)
2005	{
2006	val.lattice_val = CONSTANT;
2007	val.mask = mask;
2008	/* ??? Delay building trees here. */
2009	val.value = wide_int_to_tree (type, cst: value);
2010	}
2011	else
2012	{
2013	val.lattice_val = VARYING;
2014	val.value = NULL_TREE;
2015	val.mask = -1;
2016	}
2017	return val;
2018	}
2019
2020	/* Return the propagation value when applying the operation CODE to
2021	the values RHS1 and RHS2 yielding type TYPE. */
2022
2023	static ccp_prop_value_t
2024	bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2)
2025	{
2026	ccp_prop_value_t r1val = get_value_for_expr (expr: rhs1, for_bits_p: true);
2027	ccp_prop_value_t r2val = get_value_for_expr (expr: rhs2, for_bits_p: true);
2028	widest_int value, mask;
2029	ccp_prop_value_t val;
2030
2031	if (r1val.lattice_val == UNDEFINED
2032	|| r2val.lattice_val == UNDEFINED)
2033	{
2034	val.lattice_val = VARYING;
2035	val.value = NULL_TREE;
2036	val.mask = -1;
2037	return val;
2038	}
2039
2040	gcc_assert ((r1val.lattice_val == CONSTANT
2041	&& TREE_CODE (r1val.value) == INTEGER_CST)
2042	|| wi::sext (r1val.mask,
2043	TYPE_PRECISION (TREE_TYPE (rhs1))) == -1);
2044	gcc_assert ((r2val.lattice_val == CONSTANT
2045	&& TREE_CODE (r2val.value) == INTEGER_CST)
2046	|| wi::sext (r2val.mask,
2047	TYPE_PRECISION (TREE_TYPE (rhs2))) == -1);
2048	bit_value_binop (code, TYPE_SIGN (type), TYPE_PRECISION (type), val: &value, mask: &mask,
2049	TYPE_SIGN (TREE_TYPE (rhs1)), TYPE_PRECISION (TREE_TYPE (rhs1)),
2050	r1val: value_to_wide_int (val: r1val), r1mask: r1val.mask,
2051	TYPE_SIGN (TREE_TYPE (rhs2)), TYPE_PRECISION (TREE_TYPE (rhs2)),
2052	r2val: value_to_wide_int (val: r2val), r2mask: r2val.mask);
2053
2054	/* (x * x) & 2 == 0. */
2055	if (code == MULT_EXPR && rhs1 == rhs2 && TYPE_PRECISION (type) > 1)
2056	{
2057	widest_int m = 2;
2058	if (wi::sext (x: mask, TYPE_PRECISION (type)) != -1)
2059	value = wi::bit_and_not (x: value, y: m);
2060	else
2061	value = 0;
2062	mask = wi::bit_and_not (x: mask, y: m);
2063	}
2064
2065	if (wi::sext (x: mask, TYPE_PRECISION (type)) != -1)
2066	{
2067	val.lattice_val = CONSTANT;
2068	val.mask = mask;
2069	/* ??? Delay building trees here. */
2070	val.value = wide_int_to_tree (type, cst: value);
2071	}
2072	else
2073	{
2074	val.lattice_val = VARYING;
2075	val.value = NULL_TREE;
2076	val.mask = -1;
2077	}
2078	return val;
2079	}
2080
2081	/* Return the propagation value for __builtin_assume_aligned
2082	and functions with assume_aligned or alloc_aligned attribute.
2083	For __builtin_assume_aligned, ATTR is NULL_TREE,
2084	for assume_aligned attribute ATTR is non-NULL and ALLOC_ALIGNED
2085	is false, for alloc_aligned attribute ATTR is non-NULL and
2086	ALLOC_ALIGNED is true. */
2087
2088	static ccp_prop_value_t
2089	bit_value_assume_aligned (gimple *stmt, tree attr, ccp_prop_value_t ptrval,
2090	bool alloc_aligned)
2091	{
2092	tree align, misalign = NULL_TREE, type;
2093	unsigned HOST_WIDE_INT aligni, misaligni = 0;
2094	ccp_prop_value_t alignval;
2095	widest_int value, mask;
2096	ccp_prop_value_t val;
2097
2098	if (attr == NULL_TREE)
2099	{
2100	tree ptr = gimple_call_arg (gs: stmt, index: 0);
2101	type = TREE_TYPE (ptr);
2102	ptrval = get_value_for_expr (expr: ptr, for_bits_p: true);
2103	}
2104	else
2105	{
2106	tree lhs = gimple_call_lhs (gs: stmt);
2107	type = TREE_TYPE (lhs);
2108	}
2109
2110	if (ptrval.lattice_val == UNDEFINED)
2111	return ptrval;
2112	gcc_assert ((ptrval.lattice_val == CONSTANT
2113	&& TREE_CODE (ptrval.value) == INTEGER_CST)
2114	|| wi::sext (ptrval.mask, TYPE_PRECISION (type)) == -1);
2115	if (attr == NULL_TREE)
2116	{
2117	/* Get aligni and misaligni from __builtin_assume_aligned. */
2118	align = gimple_call_arg (gs: stmt, index: 1);
2119	if (!tree_fits_uhwi_p (align))
2120	return ptrval;
2121	aligni = tree_to_uhwi (align);
2122	if (gimple_call_num_args (gs: stmt) > 2)
2123	{
2124	misalign = gimple_call_arg (gs: stmt, index: 2);
2125	if (!tree_fits_uhwi_p (misalign))
2126	return ptrval;
2127	misaligni = tree_to_uhwi (misalign);
2128	}
2129	}
2130	else
2131	{
2132	/* Get aligni and misaligni from assume_aligned or
2133	alloc_align attributes. */
2134	if (TREE_VALUE (attr) == NULL_TREE)
2135	return ptrval;
2136	attr = TREE_VALUE (attr);
2137	align = TREE_VALUE (attr);
2138	if (!tree_fits_uhwi_p (align))
2139	return ptrval;
2140	aligni = tree_to_uhwi (align);
2141	if (alloc_aligned)
2142	{
2143	if (aligni == 0 || aligni > gimple_call_num_args (gs: stmt))
2144	return ptrval;
2145	align = gimple_call_arg (gs: stmt, index: aligni - 1);
2146	if (!tree_fits_uhwi_p (align))
2147	return ptrval;
2148	aligni = tree_to_uhwi (align);
2149	}
2150	else if (TREE_CHAIN (attr) && TREE_VALUE (TREE_CHAIN (attr)))
2151	{
2152	misalign = TREE_VALUE (TREE_CHAIN (attr));
2153	if (!tree_fits_uhwi_p (misalign))
2154	return ptrval;
2155	misaligni = tree_to_uhwi (misalign);
2156	}
2157	}
2158	if (aligni <= 1 || (aligni & (aligni - 1)) != 0 || misaligni >= aligni)
2159	return ptrval;
2160
2161	align = build_int_cst_type (type, -aligni);
2162	alignval = get_value_for_expr (expr: align, for_bits_p: true);
2163	bit_value_binop (code: BIT_AND_EXPR, TYPE_SIGN (type), TYPE_PRECISION (type), val: &value, mask: &mask,
2164	TYPE_SIGN (type), TYPE_PRECISION (type), r1val: value_to_wide_int (val: ptrval), r1mask: ptrval.mask,
2165	TYPE_SIGN (type), TYPE_PRECISION (type), r2val: value_to_wide_int (val: alignval), r2mask: alignval.mask);
2166
2167	if (wi::sext (x: mask, TYPE_PRECISION (type)) != -1)
2168	{
2169	val.lattice_val = CONSTANT;
2170	val.mask = mask;
2171	gcc_assert ((mask.to_uhwi () & (aligni - 1)) == 0);
2172	gcc_assert ((value.to_uhwi () & (aligni - 1)) == 0);
2173	value |= misaligni;
2174	/* ??? Delay building trees here. */
2175	val.value = wide_int_to_tree (type, cst: value);
2176	}
2177	else
2178	{
2179	val.lattice_val = VARYING;
2180	val.value = NULL_TREE;
2181	val.mask = -1;
2182	}
2183	return val;
2184	}
2185
2186	/* Evaluate statement STMT.
2187	Valid only for assignments, calls, conditionals, and switches. */
2188
2189	static ccp_prop_value_t
2190	evaluate_stmt (gimple *stmt)
2191	{
2192	ccp_prop_value_t val;
2193	tree simplified = NULL_TREE;
2194	ccp_lattice_t likelyvalue = likely_value (stmt);
2195	bool is_constant = false;
2196	unsigned int align;
2197	bool ignore_return_flags = false;
2198
2199	if (dump_file && (dump_flags & TDF_DETAILS))
2200	{
2201	fprintf (stream: dump_file, format: "which is likely ");
2202	switch (likelyvalue)
2203	{
2204	case CONSTANT:
2205	fprintf (stream: dump_file, format: "CONSTANT");
2206	break;
2207	case UNDEFINED:
2208	fprintf (stream: dump_file, format: "UNDEFINED");
2209	break;
2210	case VARYING:
2211	fprintf (stream: dump_file, format: "VARYING");
2212	break;
2213	default:;
2214	}
2215	fprintf (stream: dump_file, format: "\n");
2216	}
2217
2218	/* If the statement is likely to have a CONSTANT result, then try
2219	to fold the statement to determine the constant value. */
2220	/* FIXME. This is the only place that we call ccp_fold.
2221	Since likely_value never returns CONSTANT for calls, we will
2222	not attempt to fold them, including builtins that may profit. */
2223	if (likelyvalue == CONSTANT)
2224	{
2225	fold_defer_overflow_warnings ();
2226	simplified = ccp_fold (stmt);
2227	if (simplified
2228	&& TREE_CODE (simplified) == SSA_NAME)
2229	{
2230	/* We may not use values of something that may be simulated again,
2231	see valueize_op_1. */
2232	if (SSA_NAME_IS_DEFAULT_DEF (simplified)
2233	|| ! prop_simulate_again_p (SSA_NAME_DEF_STMT (simplified)))
2234	{
2235	ccp_prop_value_t *val = get_value (var: simplified);
2236	if (val && val->lattice_val != VARYING)
2237	{
2238	fold_undefer_overflow_warnings (true, stmt, 0);
2239	return *val;
2240	}
2241	}
2242	else
2243	/* We may also not place a non-valueized copy in the lattice
2244	as that might become stale if we never re-visit this stmt. */
2245	simplified = NULL_TREE;
2246	}
2247	is_constant = simplified && is_gimple_min_invariant (simplified);
2248	fold_undefer_overflow_warnings (is_constant, stmt, 0);
2249	if (is_constant)
2250	{
2251	/* The statement produced a constant value. */
2252	val.lattice_val = CONSTANT;
2253	val.value = simplified;
2254	val.mask = 0;
2255	return val;
2256	}
2257	}
2258	/* If the statement is likely to have a VARYING result, then do not
2259	bother folding the statement. */
2260	else if (likelyvalue == VARYING)
2261	{
2262	enum gimple_code code = gimple_code (g: stmt);
2263	if (code == GIMPLE_ASSIGN)
2264	{
2265	enum tree_code subcode = gimple_assign_rhs_code (gs: stmt);
2266
2267	/* Other cases cannot satisfy is_gimple_min_invariant
2268	without folding. */
2269	if (get_gimple_rhs_class (code: subcode) == GIMPLE_SINGLE_RHS)
2270	simplified = gimple_assign_rhs1 (gs: stmt);
2271	}
2272	else if (code == GIMPLE_SWITCH)
2273	simplified = gimple_switch_index (gs: as_a <gswitch *> (p: stmt));
2274	else
2275	/* These cannot satisfy is_gimple_min_invariant without folding. */
2276	gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND);
2277	is_constant = simplified && is_gimple_min_invariant (simplified);
2278	if (is_constant)
2279	{
2280	/* The statement produced a constant value. */
2281	val.lattice_val = CONSTANT;
2282	val.value = simplified;
2283	val.mask = 0;
2284	}
2285	}
2286	/* If the statement result is likely UNDEFINED, make it so. */
2287	else if (likelyvalue == UNDEFINED)
2288	{
2289	val.lattice_val = UNDEFINED;
2290	val.value = NULL_TREE;
2291	val.mask = 0;
2292	return val;
2293	}
2294
2295	/* Resort to simplification for bitwise tracking. */
2296	if (flag_tree_bit_ccp
2297	&& (likelyvalue == CONSTANT || is_gimple_call (gs: stmt)
2298	|| (gimple_assign_single_p (gs: stmt)
2299	&& gimple_assign_rhs_code (gs: stmt) == ADDR_EXPR))
2300	&& !is_constant)
2301	{
2302	enum gimple_code code = gimple_code (g: stmt);
2303	val.lattice_val = VARYING;
2304	val.value = NULL_TREE;
2305	val.mask = -1;
2306	if (code == GIMPLE_ASSIGN)
2307	{
2308	enum tree_code subcode = gimple_assign_rhs_code (gs: stmt);
2309	tree rhs1 = gimple_assign_rhs1 (gs: stmt);
2310	tree lhs = gimple_assign_lhs (gs: stmt);
2311	if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
2312	|| POINTER_TYPE_P (TREE_TYPE (lhs)))
2313	&& (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2314	|| POINTER_TYPE_P (TREE_TYPE (rhs1))))
2315	switch (get_gimple_rhs_class (code: subcode))
2316	{
2317	case GIMPLE_SINGLE_RHS:
2318	val = get_value_for_expr (expr: rhs1, for_bits_p: true);
2319	break;
2320
2321	case GIMPLE_UNARY_RHS:
2322	val = bit_value_unop (code: subcode, TREE_TYPE (lhs), rhs: rhs1);
2323	break;
2324
2325	case GIMPLE_BINARY_RHS:
2326	val = bit_value_binop (code: subcode, TREE_TYPE (lhs), rhs1,
2327	rhs2: gimple_assign_rhs2 (gs: stmt));
2328	break;
2329
2330	default:;
2331	}
2332	}
2333	else if (code == GIMPLE_COND)
2334	{
2335	enum tree_code code = gimple_cond_code (gs: stmt);
2336	tree rhs1 = gimple_cond_lhs (gs: stmt);
2337	tree rhs2 = gimple_cond_rhs (gs: stmt);
2338	if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2339	|| POINTER_TYPE_P (TREE_TYPE (rhs1)))
2340	val = bit_value_binop (code, TREE_TYPE (rhs1), rhs1, rhs2);
2341	}
2342	else if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
2343	{
2344	tree fndecl = gimple_call_fndecl (gs: stmt);
2345	switch (DECL_FUNCTION_CODE (decl: fndecl))
2346	{
2347	case BUILT_IN_MALLOC:
2348	case BUILT_IN_REALLOC:
2349	case BUILT_IN_CALLOC:
2350	case BUILT_IN_STRDUP:
2351	case BUILT_IN_STRNDUP:
2352	val.lattice_val = CONSTANT;
2353	val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
2354	val.mask = ~((HOST_WIDE_INT) MALLOC_ABI_ALIGNMENT
2355	/ BITS_PER_UNIT - 1);
2356	break;
2357
2358	CASE_BUILT_IN_ALLOCA:
2359	align = (DECL_FUNCTION_CODE (decl: fndecl) == BUILT_IN_ALLOCA
2360	? BIGGEST_ALIGNMENT
2361	: TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)));
2362	val.lattice_val = CONSTANT;
2363	val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
2364	val.mask = ~((HOST_WIDE_INT) align / BITS_PER_UNIT - 1);
2365	break;
2366
2367	case BUILT_IN_ASSUME_ALIGNED:
2368	val = bit_value_assume_aligned (stmt, NULL_TREE, ptrval: val, alloc_aligned: false);
2369	ignore_return_flags = true;
2370	break;
2371
2372	case BUILT_IN_ALIGNED_ALLOC:
2373	case BUILT_IN_GOMP_ALLOC:
2374	{
2375	tree align = get_constant_value (var: gimple_call_arg (gs: stmt, index: 0));
2376	if (align
2377	&& tree_fits_uhwi_p (align))
2378	{
2379	unsigned HOST_WIDE_INT aligni = tree_to_uhwi (align);
2380	if (aligni > 1
2381	/* align must be power-of-two */
2382	&& (aligni & (aligni - 1)) == 0)
2383	{
2384	val.lattice_val = CONSTANT;
2385	val.value = build_int_cst (ptr_type_node, 0);
2386	val.mask = -aligni;
2387	}
2388	}
2389	break;
2390	}
2391
2392	case BUILT_IN_BSWAP16:
2393	case BUILT_IN_BSWAP32:
2394	case BUILT_IN_BSWAP64:
2395	case BUILT_IN_BSWAP128:
2396	val = get_value_for_expr (expr: gimple_call_arg (gs: stmt, index: 0), for_bits_p: true);
2397	if (val.lattice_val == UNDEFINED)
2398	break;
2399	else if (val.lattice_val == CONSTANT
2400	&& val.value
2401	&& TREE_CODE (val.value) == INTEGER_CST)
2402	{
2403	tree type = TREE_TYPE (gimple_call_lhs (stmt));
2404	int prec = TYPE_PRECISION (type);
2405	wide_int wval = wi::to_wide (t: val.value);
2406	val.value
2407	= wide_int_to_tree (type,
2408	cst: wi::bswap (x: wide_int::from (x: wval, precision: prec,
2409	sgn: UNSIGNED)));
2410	val.mask
2411	= widest_int::from (x: wi::bswap (x: wide_int::from (x: val.mask,
2412	precision: prec,
2413	sgn: UNSIGNED)),
2414	sgn: UNSIGNED);
2415	if (wi::sext (x: val.mask, offset: prec) != -1)
2416	break;
2417	}
2418	val.lattice_val = VARYING;
2419	val.value = NULL_TREE;
2420	val.mask = -1;
2421	break;
2422
2423	default:;
2424	}
2425	}
2426	if (is_gimple_call (gs: stmt) && gimple_call_lhs (gs: stmt))
2427	{
2428	tree fntype = gimple_call_fntype (gs: stmt);
2429	if (fntype)
2430	{
2431	tree attrs = lookup_attribute (attr_name: "assume_aligned",
2432	TYPE_ATTRIBUTES (fntype));
2433	if (attrs)
2434	val = bit_value_assume_aligned (stmt, attr: attrs, ptrval: val, alloc_aligned: false);
2435	attrs = lookup_attribute (attr_name: "alloc_align",
2436	TYPE_ATTRIBUTES (fntype));
2437	if (attrs)
2438	val = bit_value_assume_aligned (stmt, attr: attrs, ptrval: val, alloc_aligned: true);
2439	}
2440	int flags = ignore_return_flags
2441	? 0 : gimple_call_return_flags (as_a <gcall *> (p: stmt));
2442	if (flags & ERF_RETURNS_ARG
2443	&& (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (gs: stmt))
2444	{
2445	val = get_value_for_expr
2446	(expr: gimple_call_arg (gs: stmt,
2447	index: flags & ERF_RETURN_ARG_MASK), for_bits_p: true);
2448	}
2449	}
2450	is_constant = (val.lattice_val == CONSTANT);
2451	}
2452
2453	if (flag_tree_bit_ccp
2454	&& ((is_constant && TREE_CODE (val.value) == INTEGER_CST)
2455	|| !is_constant)
2456	&& gimple_get_lhs (stmt)
2457	&& TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME)
2458	{
2459	tree lhs = gimple_get_lhs (stmt);
2460	wide_int nonzero_bits = get_nonzero_bits (lhs);
2461	if (nonzero_bits != -1)
2462	{
2463	if (!is_constant)
2464	{
2465	val.lattice_val = CONSTANT;
2466	val.value = build_zero_cst (TREE_TYPE (lhs));
2467	val.mask = extend_mask (nonzero_bits, TYPE_SIGN (TREE_TYPE (lhs)));
2468	is_constant = true;
2469	}
2470	else
2471	{
2472	if (wi::bit_and_not (x: wi::to_wide (t: val.value), y: nonzero_bits) != 0)
2473	val.value = wide_int_to_tree (TREE_TYPE (lhs),
2474	cst: nonzero_bits
2475	& wi::to_wide (t: val.value));
2476	if (nonzero_bits == 0)
2477	val.mask = 0;
2478	else
2479	val.mask = val.mask & extend_mask (nonzero_bits,
2480	TYPE_SIGN (TREE_TYPE (lhs)));
2481	}
2482	}
2483	}
2484
2485	/* The statement produced a nonconstant value. */
2486	if (!is_constant)
2487	{
2488	/* The statement produced a copy. */
2489	if (simplified && TREE_CODE (simplified) == SSA_NAME
2490	&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (simplified))
2491	{
2492	val.lattice_val = CONSTANT;
2493	val.value = simplified;
2494	val.mask = -1;
2495	}
2496	/* The statement is VARYING. */
2497	else
2498	{
2499	val.lattice_val = VARYING;
2500	val.value = NULL_TREE;
2501	val.mask = -1;
2502	}
2503	}
2504
2505	return val;
2506	}
2507
2508	typedef hash_table<nofree_ptr_hash<gimple> > gimple_htab;
2509
2510	/* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
2511	each matching BUILT_IN_STACK_RESTORE. Mark visited phis in VISITED. */
2512
2513	static void
2514	insert_clobber_before_stack_restore (tree saved_val, tree var,
2515	gimple_htab **visited)
2516	{
2517	gimple *stmt;
2518	gassign *clobber_stmt;
2519	tree clobber;
2520	imm_use_iterator iter;
2521	gimple_stmt_iterator i;
2522	gimple **slot;
2523
2524	FOR_EACH_IMM_USE_STMT (stmt, iter, saved_val)
2525	if (gimple_call_builtin_p (stmt, BUILT_IN_STACK_RESTORE))
2526	{
2527	clobber = build_clobber (TREE_TYPE (var), CLOBBER_EOL);
2528	clobber_stmt = gimple_build_assign (var, clobber);
2529
2530	i = gsi_for_stmt (stmt);
2531	gsi_insert_before (&i, clobber_stmt, GSI_SAME_STMT);
2532	}
2533	else if (gimple_code (g: stmt) == GIMPLE_PHI)
2534	{
2535	if (!*visited)
2536	*visited = new gimple_htab (10);
2537
2538	slot = (*visited)->find_slot (value: stmt, insert: INSERT);
2539	if (*slot != NULL)
2540	continue;
2541
2542	*slot = stmt;
2543	insert_clobber_before_stack_restore (saved_val: gimple_phi_result (gs: stmt), var,
2544	visited);
2545	}
2546	else if (gimple_assign_ssa_name_copy_p (stmt))
2547	insert_clobber_before_stack_restore (saved_val: gimple_assign_lhs (gs: stmt), var,
2548	visited);
2549	}
2550
2551	/* Advance the iterator to the previous non-debug gimple statement in the same
2552	or dominating basic block. */
2553
2554	static inline void
2555	gsi_prev_dom_bb_nondebug (gimple_stmt_iterator *i)
2556	{
2557	basic_block dom;
2558
2559	gsi_prev_nondebug (i);
2560	while (gsi_end_p (i: *i))
2561	{
2562	dom = get_immediate_dominator (CDI_DOMINATORS, gsi_bb (i: *i));
2563	if (dom == NULL || dom == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2564	return;
2565
2566	*i = gsi_last_bb (bb: dom);
2567	}
2568	}
2569
2570	/* Find a BUILT_IN_STACK_SAVE dominating gsi_stmt (I), and insert
2571	a clobber of VAR before each matching BUILT_IN_STACK_RESTORE.
2572
2573	It is possible that BUILT_IN_STACK_SAVE cannot be found in a dominator when
2574	a previous pass (such as DOM) duplicated it along multiple paths to a BB.
2575	In that case the function gives up without inserting the clobbers. */
2576
2577	static void
2578	insert_clobbers_for_var (gimple_stmt_iterator i, tree var)
2579	{
2580	gimple *stmt;
2581	tree saved_val;
2582	gimple_htab *visited = NULL;
2583
2584	for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (i: &i))
2585	{
2586	stmt = gsi_stmt (i);
2587
2588	if (!gimple_call_builtin_p (stmt, BUILT_IN_STACK_SAVE))
2589	continue;
2590
2591	saved_val = gimple_call_lhs (gs: stmt);
2592	if (saved_val == NULL_TREE)
2593	continue;
2594
2595	insert_clobber_before_stack_restore (saved_val, var, visited: &visited);
2596	break;
2597	}
2598
2599	delete visited;
2600	}
2601
2602	/* Detects a __builtin_alloca_with_align with constant size argument. Declares
2603	fixed-size array and returns the address, if found, otherwise returns
2604	NULL_TREE. */
2605
2606	static tree
2607	fold_builtin_alloca_with_align (gimple *stmt)
2608	{
2609	unsigned HOST_WIDE_INT size, threshold, n_elem;
2610	tree lhs, arg, block, var, elem_type, array_type;
2611
2612	/* Get lhs. */
2613	lhs = gimple_call_lhs (gs: stmt);
2614	if (lhs == NULL_TREE)
2615	return NULL_TREE;
2616
2617	/* Detect constant argument. */
2618	arg = get_constant_value (var: gimple_call_arg (gs: stmt, index: 0));
2619	if (arg == NULL_TREE
2620	|| TREE_CODE (arg) != INTEGER_CST
2621	|| !tree_fits_uhwi_p (arg))
2622	return NULL_TREE;
2623
2624	size = tree_to_uhwi (arg);
2625
2626	/* Heuristic: don't fold large allocas. */
2627	threshold = (unsigned HOST_WIDE_INT)param_large_stack_frame;
2628	/* In case the alloca is located at function entry, it has the same lifetime
2629	as a declared array, so we allow a larger size. */
2630	block = gimple_block (g: stmt);
2631	if (!(cfun->after_inlining
2632	&& block
2633	&& TREE_CODE (BLOCK_SUPERCONTEXT (block)) == FUNCTION_DECL))
2634	threshold /= 10;
2635	if (size > threshold)
2636	return NULL_TREE;
2637
2638	/* We have to be able to move points-to info. We used to assert
2639	that we can but IPA PTA might end up with two UIDs here
2640	as it might need to handle more than one instance being
2641	live at the same time. Instead of trying to detect this case
2642	(using the first UID would be OK) just give up for now. */
2643	struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs);
2644	unsigned uid = 0;
2645	if (pi != NULL
2646	&& !pi->pt.anything
2647	&& !pt_solution_singleton_or_null_p (&pi->pt, &uid))
2648	return NULL_TREE;
2649
2650	/* Declare array. */
2651	elem_type = build_nonstandard_integer_type (BITS_PER_UNIT, 1);
2652	n_elem = size * 8 / BITS_PER_UNIT;
2653	array_type = build_array_type_nelts (elem_type, n_elem);
2654
2655	if (tree ssa_name = SSA_NAME_IDENTIFIER (lhs))
2656	{
2657	/* Give the temporary a name derived from the name of the VLA
2658	declaration so it can be referenced in diagnostics. */
2659	const char *name = IDENTIFIER_POINTER (ssa_name);
2660	var = create_tmp_var (array_type, name);
2661	}
2662	else
2663	var = create_tmp_var (array_type);
2664
2665	if (gimple *lhsdef = SSA_NAME_DEF_STMT (lhs))
2666	{
2667	/* Set the temporary's location to that of the VLA declaration
2668	so it can be pointed to in diagnostics. */
2669	location_t loc = gimple_location (g: lhsdef);
2670	DECL_SOURCE_LOCATION (var) = loc;
2671	}
2672
2673	SET_DECL_ALIGN (var, TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)));
2674	if (uid != 0)
2675	SET_DECL_PT_UID (var, uid);
2676
2677	/* Fold alloca to the address of the array. */
2678	return fold_convert (TREE_TYPE (lhs), build_fold_addr_expr (var));
2679	}
2680
2681	/* Fold the stmt at *GSI with CCP specific information that propagating
2682	and regular folding does not catch. */
2683
2684	bool
2685	ccp_folder::fold_stmt (gimple_stmt_iterator *gsi)
2686	{
2687	gimple *stmt = gsi_stmt (i: *gsi);
2688
2689	switch (gimple_code (g: stmt))
2690	{
2691	case GIMPLE_COND:
2692	{
2693	gcond *cond_stmt = as_a <gcond *> (p: stmt);
2694	ccp_prop_value_t val;
2695	/* Statement evaluation will handle type mismatches in constants
2696	more gracefully than the final propagation. This allows us to
2697	fold more conditionals here. */
2698	val = evaluate_stmt (stmt);
2699	if (val.lattice_val != CONSTANT
2700	|| val.mask != 0)
2701	return false;
2702
2703	if (dump_file)
2704	{
2705	fprintf (stream: dump_file, format: "Folding predicate ");
2706	print_gimple_expr (dump_file, stmt, 0);
2707	fprintf (stream: dump_file, format: " to ");
2708	print_generic_expr (dump_file, val.value);
2709	fprintf (stream: dump_file, format: "\n");
2710	}
2711
2712	if (integer_zerop (val.value))
2713	gimple_cond_make_false (gs: cond_stmt);
2714	else
2715	gimple_cond_make_true (gs: cond_stmt);
2716
2717	return true;
2718	}
2719
2720	case GIMPLE_CALL:
2721	{
2722	tree lhs = gimple_call_lhs (gs: stmt);
2723	int flags = gimple_call_flags (stmt);
2724	tree val;
2725	tree argt;
2726	bool changed = false;
2727	unsigned i;
2728
2729	/* If the call was folded into a constant make sure it goes
2730	away even if we cannot propagate into all uses because of
2731	type issues. */
2732	if (lhs
2733	&& TREE_CODE (lhs) == SSA_NAME
2734	&& (val = get_constant_value (var: lhs))
2735	/* Don't optimize away calls that have side-effects. */
2736	&& (flags & (ECF_CONST|ECF_PURE)) != 0
2737	&& (flags & ECF_LOOPING_CONST_OR_PURE) == 0)
2738	{
2739	tree new_rhs = unshare_expr (val);
2740	if (!useless_type_conversion_p (TREE_TYPE (lhs),
2741	TREE_TYPE (new_rhs)))
2742	new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
2743	gimplify_and_update_call_from_tree (gsi, new_rhs);
2744	return true;
2745	}
2746
2747	/* Internal calls provide no argument types, so the extra laxity
2748	for normal calls does not apply. */
2749	if (gimple_call_internal_p (gs: stmt))
2750	return false;
2751
2752	/* The heuristic of fold_builtin_alloca_with_align differs before and
2753	after inlining, so we don't require the arg to be changed into a
2754	constant for folding, but just to be constant. */
2755	if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN)
2756	|| gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
2757	{
2758	tree new_rhs = fold_builtin_alloca_with_align (stmt);
2759	if (new_rhs)
2760	{
2761	gimplify_and_update_call_from_tree (gsi, new_rhs);
2762	tree var = TREE_OPERAND (TREE_OPERAND (new_rhs, 0),0);
2763	insert_clobbers_for_var (i: *gsi, var);
2764	return true;
2765	}
2766	}
2767
2768	/* If there's no extra info from an assume_aligned call,
2769	drop it so it doesn't act as otherwise useless dataflow
2770	barrier. */
2771	if (gimple_call_builtin_p (stmt, BUILT_IN_ASSUME_ALIGNED))
2772	{
2773	tree ptr = gimple_call_arg (gs: stmt, index: 0);
2774	ccp_prop_value_t ptrval = get_value_for_expr (expr: ptr, for_bits_p: true);
2775	if (ptrval.lattice_val == CONSTANT
2776	&& TREE_CODE (ptrval.value) == INTEGER_CST
2777	&& ptrval.mask != 0)
2778	{
2779	ccp_prop_value_t val
2780	= bit_value_assume_aligned (stmt, NULL_TREE, ptrval, alloc_aligned: false);
2781	unsigned int ptralign = least_bit_hwi (x: ptrval.mask.to_uhwi ());
2782	unsigned int align = least_bit_hwi (x: val.mask.to_uhwi ());
2783	if (ptralign == align
2784	&& ((TREE_INT_CST_LOW (ptrval.value) & (align - 1))
2785	== (TREE_INT_CST_LOW (val.value) & (align - 1))))
2786	{
2787	replace_call_with_value (gsi, ptr);
2788	return true;
2789	}
2790	}
2791	}
2792
2793	/* Propagate into the call arguments. Compared to replace_uses_in
2794	this can use the argument slot types for type verification
2795	instead of the current argument type. We also can safely
2796	drop qualifiers here as we are dealing with constants anyway. */
2797	argt = TYPE_ARG_TYPES (gimple_call_fntype (stmt));
2798	for (i = 0; i < gimple_call_num_args (gs: stmt) && argt;
2799	++i, argt = TREE_CHAIN (argt))
2800	{
2801	tree arg = gimple_call_arg (gs: stmt, index: i);
2802	if (TREE_CODE (arg) == SSA_NAME
2803	&& (val = get_constant_value (var: arg))
2804	&& useless_type_conversion_p
2805	(TYPE_MAIN_VARIANT (TREE_VALUE (argt)),
2806	TYPE_MAIN_VARIANT (TREE_TYPE (val))))
2807	{
2808	gimple_call_set_arg (gs: stmt, index: i, arg: unshare_expr (val));
2809	changed = true;
2810	}
2811	}
2812
2813	return changed;
2814	}
2815
2816	case GIMPLE_ASSIGN:
2817	{
2818	tree lhs = gimple_assign_lhs (gs: stmt);
2819	tree val;
2820
2821	/* If we have a load that turned out to be constant replace it
2822	as we cannot propagate into all uses in all cases. */
2823	if (gimple_assign_single_p (gs: stmt)
2824	&& TREE_CODE (lhs) == SSA_NAME
2825	&& (val = get_constant_value (var: lhs)))
2826	{
2827	tree rhs = unshare_expr (val);
2828	if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2829	rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2830	gimple_assign_set_rhs_from_tree (gsi, rhs);
2831	return true;
2832	}
2833
2834	return false;
2835	}
2836
2837	default:
2838	return false;
2839	}
2840	}
2841
2842	/* Visit the assignment statement STMT. Set the value of its LHS to the
2843	value computed by the RHS and store LHS in *OUTPUT_P. If STMT
2844	creates virtual definitions, set the value of each new name to that
2845	of the RHS (if we can derive a constant out of the RHS).
2846	Value-returning call statements also perform an assignment, and
2847	are handled here. */
2848
2849	static enum ssa_prop_result
2850	visit_assignment (gimple *stmt, tree *output_p)
2851	{
2852	ccp_prop_value_t val;
2853	enum ssa_prop_result retval = SSA_PROP_NOT_INTERESTING;
2854
2855	tree lhs = gimple_get_lhs (stmt);
2856	if (TREE_CODE (lhs) == SSA_NAME)
2857	{
2858	/* Evaluate the statement, which could be
2859	either a GIMPLE_ASSIGN or a GIMPLE_CALL. */
2860	val = evaluate_stmt (stmt);
2861
2862	/* If STMT is an assignment to an SSA_NAME, we only have one
2863	value to set. */
2864	if (set_lattice_value (var: lhs, new_val: &val))
2865	{
2866	*output_p = lhs;
2867	if (val.lattice_val == VARYING)
2868	retval = SSA_PROP_VARYING;
2869	else
2870	retval = SSA_PROP_INTERESTING;
2871	}
2872	}
2873
2874	return retval;
2875	}
2876
2877
2878	/* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING
2879	if it can determine which edge will be taken. Otherwise, return
2880	SSA_PROP_VARYING. */
2881
2882	static enum ssa_prop_result
2883	visit_cond_stmt (gimple *stmt, edge *taken_edge_p)
2884	{
2885	ccp_prop_value_t val;
2886	basic_block block;
2887
2888	block = gimple_bb (g: stmt);
2889	val = evaluate_stmt (stmt);
2890	if (val.lattice_val != CONSTANT
2891	|| val.mask != 0)
2892	return SSA_PROP_VARYING;
2893
2894	/* Find which edge out of the conditional block will be taken and add it
2895	to the worklist. If no single edge can be determined statically,
2896	return SSA_PROP_VARYING to feed all the outgoing edges to the
2897	propagation engine. */
2898	*taken_edge_p = find_taken_edge (block, val.value);
2899	if (*taken_edge_p)
2900	return SSA_PROP_INTERESTING;
2901	else
2902	return SSA_PROP_VARYING;
2903	}
2904
2905
2906	/* Evaluate statement STMT. If the statement produces an output value and
2907	its evaluation changes the lattice value of its output, return
2908	SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
2909	output value.
2910
2911	If STMT is a conditional branch and we can determine its truth
2912	value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying
2913	value, return SSA_PROP_VARYING. */
2914
2915	enum ssa_prop_result
2916	ccp_propagate::visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
2917	{
2918	tree def;
2919	ssa_op_iter iter;
2920
2921	if (dump_file && (dump_flags & TDF_DETAILS))
2922	{
2923	fprintf (stream: dump_file, format: "\nVisiting statement:\n");
2924	print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2925	}
2926
2927	switch (gimple_code (g: stmt))
2928	{
2929	case GIMPLE_ASSIGN:
2930	/* If the statement is an assignment that produces a single
2931	output value, evaluate its RHS to see if the lattice value of
2932	its output has changed. */
2933	return visit_assignment (stmt, output_p);
2934
2935	case GIMPLE_CALL:
2936	/* A value-returning call also performs an assignment. */
2937	if (gimple_call_lhs (gs: stmt) != NULL_TREE)
2938	return visit_assignment (stmt, output_p);
2939	break;
2940
2941	case GIMPLE_COND:
2942	case GIMPLE_SWITCH:
2943	/* If STMT is a conditional branch, see if we can determine
2944	which branch will be taken. */
2945	/* FIXME. It appears that we should be able to optimize
2946	computed GOTOs here as well. */
2947	return visit_cond_stmt (stmt, taken_edge_p);
2948
2949	default:
2950	break;
2951	}
2952
2953	/* Any other kind of statement is not interesting for constant
2954	propagation and, therefore, not worth simulating. */
2955	if (dump_file && (dump_flags & TDF_DETAILS))
2956	fprintf (stream: dump_file, format: "No interesting values produced. Marked VARYING.\n");
2957
2958	/* Definitions made by statements other than assignments to
2959	SSA_NAMEs represent unknown modifications to their outputs.
2960	Mark them VARYING. */
2961	FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
2962	set_value_varying (def);
2963
2964	return SSA_PROP_VARYING;
2965	}
2966
2967
2968	/* Main entry point for SSA Conditional Constant Propagation. If NONZERO_P,
2969	record nonzero bits. */
2970
2971	static unsigned int
2972	do_ssa_ccp (bool nonzero_p)
2973	{
2974	unsigned int todo = 0;
2975	calculate_dominance_info (CDI_DOMINATORS);
2976
2977	ccp_initialize ();
2978	class ccp_propagate ccp_propagate;
2979	ccp_propagate.ssa_propagate ();
2980	if (ccp_finalize (nonzero_p: nonzero_p || flag_ipa_bit_cp))
2981	{
2982	todo = (TODO_cleanup_cfg | TODO_update_ssa);
2983
2984	/* ccp_finalize does not preserve loop-closed ssa. */
2985	loops_state_clear (flags: LOOP_CLOSED_SSA);
2986	}
2987
2988	free_dominance_info (CDI_DOMINATORS);
2989	return todo;
2990	}
2991
2992
2993	namespace {
2994
2995	const pass_data pass_data_ccp =
2996	{
2997	.type: GIMPLE_PASS, /* type */
2998	.name: "ccp", /* name */
2999	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
3000	.tv_id: TV_TREE_CCP, /* tv_id */
3001	.properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
3002	.properties_provided: 0, /* properties_provided */
3003	.properties_destroyed: 0, /* properties_destroyed */
3004	.todo_flags_start: 0, /* todo_flags_start */
3005	TODO_update_address_taken, /* todo_flags_finish */
3006	};
3007
3008	class pass_ccp : public gimple_opt_pass
3009	{
3010	public:
3011	pass_ccp (gcc::context *ctxt)
3012	: gimple_opt_pass (pass_data_ccp, ctxt), nonzero_p (false)
3013	{}
3014
3015	/* opt_pass methods: */
3016	opt_pass * clone () final override { return new pass_ccp (m_ctxt); }
3017	void set_pass_param (unsigned int n, bool param) final override
3018	{
3019	gcc_assert (n == 0);
3020	nonzero_p = param;
3021	}
3022	bool gate (function *) final override { return flag_tree_ccp != 0; }
3023	unsigned int execute (function *) final override
3024	{
3025	return do_ssa_ccp (nonzero_p);
3026	}
3027
3028	private:
3029	/* Determines whether the pass instance records nonzero bits. */
3030	bool nonzero_p;
3031	}; // class pass_ccp
3032
3033	} // anon namespace
3034
3035	gimple_opt_pass *
3036	make_pass_ccp (gcc::context *ctxt)
3037	{
3038	return new pass_ccp (ctxt);
3039	}
3040
3041
3042
3043	/* Try to optimize out __builtin_stack_restore. Optimize it out
3044	if there is another __builtin_stack_restore in the same basic
3045	block and no calls or ASM_EXPRs are in between, or if this block's
3046	only outgoing edge is to EXIT_BLOCK and there are no calls or
3047	ASM_EXPRs after this __builtin_stack_restore. */
3048
3049	static tree
3050	optimize_stack_restore (gimple_stmt_iterator i)
3051	{
3052	tree callee;
3053	gimple *stmt;
3054
3055	basic_block bb = gsi_bb (i);
3056	gimple *call = gsi_stmt (i);
3057
3058	if (gimple_code (g: call) != GIMPLE_CALL
3059	|| gimple_call_num_args (gs: call) != 1
3060	|| TREE_CODE (gimple_call_arg (call, 0)) != SSA_NAME
3061	|| !POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, 0))))
3062	return NULL_TREE;
3063
3064	for (gsi_next (i: &i); !gsi_end_p (i); gsi_next (i: &i))
3065	{
3066	stmt = gsi_stmt (i);
3067	if (gimple_code (g: stmt) == GIMPLE_ASM)
3068	return NULL_TREE;
3069	if (gimple_code (g: stmt) != GIMPLE_CALL)
3070	continue;
3071
3072	callee = gimple_call_fndecl (gs: stmt);
3073	if (!callee
3074	|| !fndecl_built_in_p (node: callee, klass: BUILT_IN_NORMAL)
3075	/* All regular builtins are ok, just obviously not alloca. */
3076	|| ALLOCA_FUNCTION_CODE_P (DECL_FUNCTION_CODE (callee)))
3077	return NULL_TREE;
3078
3079	if (fndecl_built_in_p (node: callee, name1: BUILT_IN_STACK_RESTORE))
3080	goto second_stack_restore;
3081	}
3082
3083	if (!gsi_end_p (i))
3084	return NULL_TREE;
3085
3086	/* Allow one successor of the exit block, or zero successors. */
3087	switch (EDGE_COUNT (bb->succs))
3088	{
3089	case 0:
3090	break;
3091	case 1:
3092	if (single_succ_edge (bb)->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
3093	return NULL_TREE;
3094	break;
3095	default:
3096	return NULL_TREE;
3097	}
3098	second_stack_restore:
3099
3100	/* If there's exactly one use, then zap the call to __builtin_stack_save.
3101	If there are multiple uses, then the last one should remove the call.
3102	In any case, whether the call to __builtin_stack_save can be removed
3103	or not is irrelevant to removing the call to __builtin_stack_restore. */
3104	if (has_single_use (var: gimple_call_arg (gs: call, index: 0)))
3105	{
3106	gimple *stack_save = SSA_NAME_DEF_STMT (gimple_call_arg (call, 0));
3107	if (is_gimple_call (gs: stack_save))
3108	{
3109	callee = gimple_call_fndecl (gs: stack_save);
3110	if (callee && fndecl_built_in_p (node: callee, name1: BUILT_IN_STACK_SAVE))
3111	{
3112	gimple_stmt_iterator stack_save_gsi;
3113	tree rhs;
3114
3115	stack_save_gsi = gsi_for_stmt (stack_save);
3116	rhs = build_int_cst (TREE_TYPE (gimple_call_arg (call, 0)), 0);
3117	replace_call_with_value (&stack_save_gsi, rhs);
3118	}
3119	}
3120	}
3121
3122	/* No effect, so the statement will be deleted. */
3123	return integer_zero_node;
3124	}
3125
3126	/* If va_list type is a simple pointer and nothing special is needed,
3127	optimize __builtin_va_start (&ap, 0) into ap = __builtin_next_arg (0),
3128	__builtin_va_end (&ap) out as NOP and __builtin_va_copy into a simple
3129	pointer assignment. */
3130
3131	static tree
3132	optimize_stdarg_builtin (gimple *call)
3133	{
3134	tree callee, lhs, rhs, cfun_va_list;
3135	bool va_list_simple_ptr;
3136	location_t loc = gimple_location (g: call);
3137
3138	callee = gimple_call_fndecl (gs: call);
3139
3140	cfun_va_list = targetm.fn_abi_va_list (callee);
3141	va_list_simple_ptr = POINTER_TYPE_P (cfun_va_list)
3142	&& (TREE_TYPE (cfun_va_list) == void_type_node
3143	|| TREE_TYPE (cfun_va_list) == char_type_node);
3144
3145	switch (DECL_FUNCTION_CODE (decl: callee))
3146	{
3147	case BUILT_IN_VA_START:
3148	if (!va_list_simple_ptr
3149	|| targetm.expand_builtin_va_start != NULL
3150	|| !builtin_decl_explicit_p (fncode: BUILT_IN_NEXT_ARG))
3151	return NULL_TREE;
3152
3153	if (gimple_call_num_args (gs: call) != 2)
3154	return NULL_TREE;
3155
3156	lhs = gimple_call_arg (gs: call, index: 0);
3157	if (!POINTER_TYPE_P (TREE_TYPE (lhs))
3158	|| TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
3159	!= TYPE_MAIN_VARIANT (cfun_va_list))
3160	return NULL_TREE;
3161
3162	lhs = build_fold_indirect_ref_loc (loc, lhs);
3163	rhs = build_call_expr_loc (loc, builtin_decl_explicit (fncode: BUILT_IN_NEXT_ARG),
3164	1, integer_zero_node);
3165	rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
3166	return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
3167
3168	case BUILT_IN_VA_COPY:
3169	if (!va_list_simple_ptr)
3170	return NULL_TREE;
3171
3172	if (gimple_call_num_args (gs: call) != 2)
3173	return NULL_TREE;
3174
3175	lhs = gimple_call_arg (gs: call, index: 0);
3176	if (!POINTER_TYPE_P (TREE_TYPE (lhs))
3177	|| TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
3178	!= TYPE_MAIN_VARIANT (cfun_va_list))
3179	return NULL_TREE;
3180
3181	lhs = build_fold_indirect_ref_loc (loc, lhs);
3182	rhs = gimple_call_arg (gs: call, index: 1);
3183	if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs))
3184	!= TYPE_MAIN_VARIANT (cfun_va_list))
3185	return NULL_TREE;
3186
3187	rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
3188	return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
3189
3190	case BUILT_IN_VA_END:
3191	/* No effect, so the statement will be deleted. */
3192	return integer_zero_node;
3193
3194	default:
3195	gcc_unreachable ();
3196	}
3197	}
3198
3199	/* Attemp to make the block of __builtin_unreachable I unreachable by changing
3200	the incoming jumps. Return true if at least one jump was changed. */
3201
3202	static bool
3203	optimize_unreachable (gimple_stmt_iterator i)
3204	{
3205	basic_block bb = gsi_bb (i);
3206	gimple_stmt_iterator gsi;
3207	gimple *stmt;
3208	edge_iterator ei;
3209	edge e;
3210	bool ret;
3211
3212	if (flag_sanitize & SANITIZE_UNREACHABLE)
3213	return false;
3214
3215	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
3216	{
3217	stmt = gsi_stmt (i: gsi);
3218
3219	if (is_gimple_debug (gs: stmt))
3220	continue;
3221
3222	if (glabel *label_stmt = dyn_cast <glabel *> (p: stmt))
3223	{
3224	/* Verify we do not need to preserve the label. */
3225	if (FORCED_LABEL (gimple_label_label (label_stmt)))
3226	return false;
3227
3228	continue;
3229	}
3230
3231	/* Only handle the case that __builtin_unreachable is the first statement
3232	in the block. We rely on DCE to remove stmts without side-effects
3233	before __builtin_unreachable. */
3234	if (gsi_stmt (i: gsi) != gsi_stmt (i))
3235	return false;
3236	}
3237
3238	ret = false;
3239	FOR_EACH_EDGE (e, ei, bb->preds)
3240	{
3241	gsi = gsi_last_bb (bb: e->src);
3242	if (gsi_end_p (i: gsi))
3243	continue;
3244
3245	stmt = gsi_stmt (i: gsi);
3246	if (gcond *cond_stmt = dyn_cast <gcond *> (p: stmt))
3247	{
3248	if (e->flags & EDGE_TRUE_VALUE)
3249	gimple_cond_make_false (gs: cond_stmt);
3250	else if (e->flags & EDGE_FALSE_VALUE)
3251	gimple_cond_make_true (gs: cond_stmt);
3252	else
3253	gcc_unreachable ();
3254	update_stmt (s: cond_stmt);
3255	}
3256	else
3257	{
3258	/* Todo: handle other cases. Note that unreachable switch case
3259	statements have already been removed. */
3260	continue;
3261	}
3262
3263	ret = true;
3264	}
3265
3266	return ret;
3267	}
3268
3269	/* Convert
3270	_1 = __atomic_fetch_or_* (ptr_6, 1, _3);
3271	_7 = ~_1;
3272	_5 = (_Bool) _7;
3273	to
3274	_1 = __atomic_fetch_or_* (ptr_6, 1, _3);
3275	_8 = _1 & 1;
3276	_5 = _8 == 0;
3277	and convert
3278	_1 = __atomic_fetch_and_* (ptr_6, ~1, _3);
3279	_7 = ~_1;
3280	_4 = (_Bool) _7;
3281	to
3282	_1 = __atomic_fetch_and_* (ptr_6, ~1, _3);
3283	_8 = _1 & 1;
3284	_4 = (_Bool) _8;
3285
3286	USE_STMT is the gimplt statement which uses the return value of
3287	__atomic_fetch_or_*. LHS is the return value of __atomic_fetch_or_*.
3288	MASK is the mask passed to __atomic_fetch_or_*.
3289	*/
3290
3291	static gimple *
3292	convert_atomic_bit_not (enum internal_fn fn, gimple *use_stmt,
3293	tree lhs, tree mask)
3294	{
3295	tree and_mask;
3296	if (fn == IFN_ATOMIC_BIT_TEST_AND_RESET)
3297	{
3298	/* MASK must be ~1. */
3299	if (!operand_equal_p (build_int_cst (TREE_TYPE (lhs),
3300	~HOST_WIDE_INT_1), mask, flags: 0))
3301	return nullptr;
3302	and_mask = build_int_cst (TREE_TYPE (lhs), 1);
3303	}
3304	else
3305	{
3306	/* MASK must be 1. */
3307	if (!operand_equal_p (build_int_cst (TREE_TYPE (lhs), 1), mask, flags: 0))
3308	return nullptr;
3309	and_mask = mask;
3310	}
3311
3312	tree use_lhs = gimple_assign_lhs (gs: use_stmt);
3313
3314	use_operand_p use_p;
3315	gimple *use_not_stmt;
3316
3317	if (!single_imm_use (var: use_lhs, use_p: &use_p, stmt: &use_not_stmt)
3318	|| !is_gimple_assign (gs: use_not_stmt))
3319	return nullptr;
3320
3321	if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_not_stmt)))
3322	return nullptr;
3323
3324	tree use_not_lhs = gimple_assign_lhs (gs: use_not_stmt);
3325	if (TREE_CODE (TREE_TYPE (use_not_lhs)) != BOOLEAN_TYPE)
3326	return nullptr;
3327
3328	gimple_stmt_iterator gsi;
3329	gsi = gsi_for_stmt (use_stmt);
3330	gsi_remove (&gsi, true);
3331	tree var = make_ssa_name (TREE_TYPE (lhs));
3332	use_stmt = gimple_build_assign (var, BIT_AND_EXPR, lhs, and_mask);
3333	gsi = gsi_for_stmt (use_not_stmt);
3334	gsi_insert_before (&gsi, use_stmt, GSI_NEW_STMT);
3335	lhs = gimple_assign_lhs (gs: use_not_stmt);
3336	gimple *g = gimple_build_assign (lhs, EQ_EXPR, var,
3337	build_zero_cst (TREE_TYPE (mask)));
3338	gsi_insert_after (&gsi, g, GSI_NEW_STMT);
3339	gsi = gsi_for_stmt (use_not_stmt);
3340	gsi_remove (&gsi, true);
3341	return use_stmt;
3342	}
3343
3344	/* match.pd function to match atomic_bit_test_and pattern which
3345	has nop_convert:
3346	_1 = __atomic_fetch_or_4 (&v, 1, 0);
3347	_2 = (int) _1;
3348	_5 = _2 & 1;
3349	*/
3350	extern bool gimple_nop_atomic_bit_test_and_p (tree, tree *,
3351	tree (*) (tree));
3352	extern bool gimple_nop_convert (tree, tree*, tree (*) (tree));
3353
3354	/* Optimize
3355	mask_2 = 1 << cnt_1;
3356	_4 = __atomic_fetch_or_* (ptr_6, mask_2, _3);
3357	_5 = _4 & mask_2;
3358	to
3359	_4 = .ATOMIC_BIT_TEST_AND_SET (ptr_6, cnt_1, 0, _3);
3360	_5 = _4;
3361	If _5 is only used in _5 != 0 or _5 == 0 comparisons, 1
3362	is passed instead of 0, and the builtin just returns a zero
3363	or 1 value instead of the actual bit.
3364	Similarly for __sync_fetch_and_or_* (without the ", _3" part
3365	in there), and/or if mask_2 is a power of 2 constant.
3366	Similarly for xor instead of or, use ATOMIC_BIT_TEST_AND_COMPLEMENT
3367	in that case. And similarly for and instead of or, except that
3368	the second argument to the builtin needs to be one's complement
3369	of the mask instead of mask. */
3370
3371	static bool
3372	optimize_atomic_bit_test_and (gimple_stmt_iterator *gsip,
3373	enum internal_fn fn, bool has_model_arg,
3374	bool after)
3375	{
3376	gimple *call = gsi_stmt (i: *gsip);
3377	tree lhs = gimple_call_lhs (gs: call);
3378	use_operand_p use_p;
3379	gimple *use_stmt;
3380	tree mask;
3381	optab optab;
3382
3383	if (!flag_inline_atomics
3384	|| optimize_debug
3385	|| !gimple_call_builtin_p (call, BUILT_IN_NORMAL)
3386	|| !lhs
3387	|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
3388	|| !single_imm_use (var: lhs, use_p: &use_p, stmt: &use_stmt)
3389	|| !is_gimple_assign (gs: use_stmt)
3390	|| !gimple_vdef (g: call))
3391	return false;
3392
3393	switch (fn)
3394	{
3395	case IFN_ATOMIC_BIT_TEST_AND_SET:
3396	optab = atomic_bit_test_and_set_optab;
3397	break;
3398	case IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT:
3399	optab = atomic_bit_test_and_complement_optab;
3400	break;
3401	case IFN_ATOMIC_BIT_TEST_AND_RESET:
3402	optab = atomic_bit_test_and_reset_optab;
3403	break;
3404	default:
3405	return false;
3406	}
3407
3408	tree bit = nullptr;
3409
3410	mask = gimple_call_arg (gs: call, index: 1);
3411	tree_code rhs_code = gimple_assign_rhs_code (gs: use_stmt);
3412	if (rhs_code != BIT_AND_EXPR)
3413	{
3414	if (rhs_code != NOP_EXPR && rhs_code != BIT_NOT_EXPR)
3415	return false;
3416
3417	tree use_lhs = gimple_assign_lhs (gs: use_stmt);
3418	if (TREE_CODE (use_lhs) == SSA_NAME
3419	&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use_lhs))
3420	return false;
3421
3422	tree use_rhs = gimple_assign_rhs1 (gs: use_stmt);
3423	if (lhs != use_rhs)
3424	return false;
3425
3426	if (optab_handler (op: optab, TYPE_MODE (TREE_TYPE (lhs)))
3427	== CODE_FOR_nothing)
3428	return false;
3429
3430	gimple *g;
3431	gimple_stmt_iterator gsi;
3432	tree var;
3433	int ibit = -1;
3434
3435	if (rhs_code == BIT_NOT_EXPR)
3436	{
3437	g = convert_atomic_bit_not (fn, use_stmt, lhs, mask);
3438	if (!g)
3439	return false;
3440	use_stmt = g;
3441	ibit = 0;
3442	}
3443	else if (TREE_CODE (TREE_TYPE (use_lhs)) == BOOLEAN_TYPE)
3444	{
3445	tree and_mask;
3446	if (fn == IFN_ATOMIC_BIT_TEST_AND_RESET)
3447	{
3448	/* MASK must be ~1. */
3449	if (!operand_equal_p (build_int_cst (TREE_TYPE (lhs),
3450	~HOST_WIDE_INT_1),
3451	mask, flags: 0))
3452	return false;
3453
3454	/* Convert
3455	_1 = __atomic_fetch_and_* (ptr_6, ~1, _3);
3456	_4 = (_Bool) _1;
3457	to
3458	_1 = __atomic_fetch_and_* (ptr_6, ~1, _3);
3459	_5 = _1 & 1;
3460	_4 = (_Bool) _5;
3461	*/
3462	and_mask = build_int_cst (TREE_TYPE (lhs), 1);
3463	}
3464	else
3465	{
3466	and_mask = build_int_cst (TREE_TYPE (lhs), 1);
3467	if (!operand_equal_p (and_mask, mask, flags: 0))
3468	return false;
3469
3470	/* Convert
3471	_1 = __atomic_fetch_or_* (ptr_6, 1, _3);
3472	_4 = (_Bool) _1;
3473	to
3474	_1 = __atomic_fetch_or_* (ptr_6, 1, _3);
3475	_5 = _1 & 1;
3476	_4 = (_Bool) _5;
3477	*/
3478	}
3479	var = make_ssa_name (TREE_TYPE (use_rhs));
3480	replace_uses_by (use_rhs, var);
3481	g = gimple_build_assign (var, BIT_AND_EXPR, use_rhs,
3482	and_mask);
3483	gsi = gsi_for_stmt (use_stmt);
3484	gsi_insert_before (&gsi, g, GSI_NEW_STMT);
3485	use_stmt = g;
3486	ibit = 0;
3487	}
3488	else if (TYPE_PRECISION (TREE_TYPE (use_lhs))
3489	<= TYPE_PRECISION (TREE_TYPE (use_rhs)))
3490	{
3491	gimple *use_nop_stmt;
3492	if (!single_imm_use (var: use_lhs, use_p: &use_p, stmt: &use_nop_stmt)
3493	|| (!is_gimple_assign (gs: use_nop_stmt)
3494	&& gimple_code (g: use_nop_stmt) != GIMPLE_COND))
3495	return false;
3496	/* Handle both
3497	_4 = _5 < 0;
3498	and
3499	if (_5 < 0)
3500	*/
3501	tree use_nop_lhs = nullptr;
3502	rhs_code = ERROR_MARK;
3503	if (is_gimple_assign (gs: use_nop_stmt))
3504	{
3505	use_nop_lhs = gimple_assign_lhs (gs: use_nop_stmt);
3506	rhs_code = gimple_assign_rhs_code (gs: use_nop_stmt);
3507	}
3508	if (!use_nop_lhs || rhs_code != BIT_AND_EXPR)
3509	{
3510	/* Also handle
3511	if (_5 < 0)
3512	*/
3513	if (use_nop_lhs
3514	&& TREE_CODE (use_nop_lhs) == SSA_NAME
3515	&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use_nop_lhs))
3516	return false;
3517	if (use_nop_lhs && rhs_code == BIT_NOT_EXPR)
3518	{
3519	/* Handle
3520	_7 = ~_2;
3521	*/
3522	g = convert_atomic_bit_not (fn, use_stmt: use_nop_stmt, lhs,
3523	mask);
3524	if (!g)
3525	return false;
3526	/* Convert
3527	_1 = __atomic_fetch_or_4 (ptr_6, 1, _3);
3528	_2 = (int) _1;
3529	_7 = ~_2;
3530	_5 = (_Bool) _7;
3531	to
3532	_1 = __atomic_fetch_or_4 (ptr_6, ~1, _3);
3533	_8 = _1 & 1;
3534	_5 = _8 == 0;
3535	and convert
3536	_1 = __atomic_fetch_and_4 (ptr_6, ~1, _3);
3537	_2 = (int) _1;
3538	_7 = ~_2;
3539	_5 = (_Bool) _7;
3540	to
3541	_1 = __atomic_fetch_and_4 (ptr_6, 1, _3);
3542	_8 = _1 & 1;
3543	_5 = _8 == 0;
3544	*/
3545	gsi = gsi_for_stmt (use_stmt);
3546	gsi_remove (&gsi, true);
3547	use_stmt = g;
3548	ibit = 0;
3549	}
3550	else
3551	{
3552	tree cmp_rhs1, cmp_rhs2;
3553	if (use_nop_lhs)
3554	{
3555	/* Handle
3556	_4 = _5 < 0;
3557	*/
3558	if (TREE_CODE (TREE_TYPE (use_nop_lhs))
3559	!= BOOLEAN_TYPE)
3560	return false;
3561	cmp_rhs1 = gimple_assign_rhs1 (gs: use_nop_stmt);
3562	cmp_rhs2 = gimple_assign_rhs2 (gs: use_nop_stmt);
3563	}
3564	else
3565	{
3566	/* Handle
3567	if (_5 < 0)
3568	*/
3569	rhs_code = gimple_cond_code (gs: use_nop_stmt);
3570	cmp_rhs1 = gimple_cond_lhs (gs: use_nop_stmt);
3571	cmp_rhs2 = gimple_cond_rhs (gs: use_nop_stmt);
3572	}
3573	if (rhs_code != GE_EXPR && rhs_code != LT_EXPR)
3574	return false;
3575	if (use_lhs != cmp_rhs1)
3576	return false;
3577	if (!integer_zerop (cmp_rhs2))
3578	return false;
3579
3580	tree and_mask;
3581
3582	unsigned HOST_WIDE_INT bytes
3583	= tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (use_rhs)));
3584	ibit = bytes * BITS_PER_UNIT - 1;
3585	unsigned HOST_WIDE_INT highest
3586	= HOST_WIDE_INT_1U << ibit;
3587
3588	if (fn == IFN_ATOMIC_BIT_TEST_AND_RESET)
3589	{
3590	/* Get the signed maximum of the USE_RHS type. */
3591	and_mask = build_int_cst (TREE_TYPE (use_rhs),
3592	highest - 1);
3593	if (!operand_equal_p (and_mask, mask, flags: 0))
3594	return false;
3595
3596	/* Convert
3597	_1 = __atomic_fetch_and_4 (ptr_6, 0x7fffffff, _3);
3598	_5 = (signed int) _1;
3599	_4 = _5 < 0 or _5 >= 0;
3600	to
3601	_1 = __atomic_fetch_and_4 (ptr_6, 0x7fffffff, _3);
3602	_6 = _1 & 0x80000000;
3603	_4 = _6 != 0 or _6 == 0;
3604	and convert
3605	_1 = __atomic_fetch_and_4 (ptr_6, 0x7fffffff, _3);
3606	_5 = (signed int) _1;
3607	if (_5 < 0 or _5 >= 0)
3608	to
3609	_1 = __atomic_fetch_and_4 (ptr_6, 0x7fffffff, _3);
3610	_6 = _1 & 0x80000000;
3611	if (_6 != 0 or _6 == 0)
3612	*/
3613	and_mask = build_int_cst (TREE_TYPE (use_rhs),
3614	highest);
3615	}
3616	else
3617	{
3618	/* Get the signed minimum of the USE_RHS type. */
3619	and_mask = build_int_cst (TREE_TYPE (use_rhs),
3620	highest);
3621	if (!operand_equal_p (and_mask, mask, flags: 0))
3622	return false;
3623
3624	/* Convert
3625	_1 = __atomic_fetch_or_4 (ptr_6, 0x80000000, _3);
3626	_5 = (signed int) _1;
3627	_4 = _5 < 0 or _5 >= 0;
3628	to
3629	_1 = __atomic_fetch_or_4 (ptr_6, 0x80000000, _3);
3630	_6 = _1 & 0x80000000;
3631	_4 = _6 != 0 or _6 == 0;
3632	and convert
3633	_1 = __atomic_fetch_or_4 (ptr_6, 0x80000000, _3);
3634	_5 = (signed int) _1;
3635	if (_5 < 0 or _5 >= 0)
3636	to
3637	_1 = __atomic_fetch_or_4 (ptr_6, 0x80000000, _3);
3638	_6 = _1 & 0x80000000;
3639	if (_6 != 0 or _6 == 0)
3640	*/
3641	}
3642	var = make_ssa_name (TREE_TYPE (use_rhs));
3643	gsi = gsi_for_stmt (use_stmt);
3644	gsi_remove (&gsi, true);
3645	g = gimple_build_assign (var, BIT_AND_EXPR, use_rhs,
3646	and_mask);
3647	gsi = gsi_for_stmt (use_nop_stmt);
3648	gsi_insert_before (&gsi, g, GSI_NEW_STMT);
3649	use_stmt = g;
3650	rhs_code = rhs_code == GE_EXPR ? EQ_EXPR : NE_EXPR;
3651	tree const_zero = build_zero_cst (TREE_TYPE (use_rhs));
3652	if (use_nop_lhs)
3653	g = gimple_build_assign (use_nop_lhs, rhs_code,
3654	var, const_zero);
3655	else
3656	g = gimple_build_cond (rhs_code, var, const_zero,
3657	nullptr, nullptr);
3658	gsi_insert_after (&gsi, g, GSI_NEW_STMT);
3659	gsi = gsi_for_stmt (use_nop_stmt);
3660	gsi_remove (&gsi, true);
3661	}
3662	}
3663	else
3664	{
3665	tree match_op[3];
3666	gimple *g;
3667	if (!gimple_nop_atomic_bit_test_and_p (use_nop_lhs,
3668	&match_op[0], NULL)
3669	|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (match_op[2])
3670	|| !single_imm_use (var: match_op[2], use_p: &use_p, stmt: &g)
3671	|| !is_gimple_assign (gs: g))
3672	return false;
3673	mask = match_op[0];
3674	if (TREE_CODE (match_op[1]) == INTEGER_CST)
3675	{
3676	ibit = tree_log2 (match_op[1]);
3677	gcc_assert (ibit >= 0);
3678	}
3679	else
3680	{
3681	g = SSA_NAME_DEF_STMT (match_op[1]);
3682	gcc_assert (is_gimple_assign (g));
3683	bit = gimple_assign_rhs2 (gs: g);
3684	}
3685	/* Convert
3686	_1 = __atomic_fetch_or_4 (ptr_6, mask, _3);
3687	_2 = (int) _1;
3688	_5 = _2 & mask;
3689	to
3690	_1 = __atomic_fetch_or_4 (ptr_6, mask, _3);
3691	_6 = _1 & mask;
3692	_5 = (int) _6;
3693	and convert
3694	_1 = ~mask_7;
3695	_2 = (unsigned int) _1;
3696	_3 = __atomic_fetch_and_4 (ptr_6, _2, 0);
3697	_4 = (int) _3;
3698	_5 = _4 & mask_7;
3699	to
3700	_1 = __atomic_fetch_and_* (ptr_6, ~mask_7, _3);
3701	_12 = _3 & mask_7;
3702	_5 = (int) _12;
3703
3704	and Convert
3705	_1 = __atomic_fetch_and_4 (ptr_6, ~mask, _3);
3706	_2 = (short int) _1;
3707	_5 = _2 & mask;
3708	to
3709	_1 = __atomic_fetch_and_4 (ptr_6, ~mask, _3);
3710	_8 = _1 & mask;
3711	_5 = (short int) _8;
3712	*/
3713	gimple_seq stmts = NULL;
3714	match_op[1] = gimple_convert (seq: &stmts,
3715	TREE_TYPE (use_rhs),
3716	op: match_op[1]);
3717	var = gimple_build (seq: &stmts, code: BIT_AND_EXPR,
3718	TREE_TYPE (use_rhs), ops: use_rhs, ops: match_op[1]);
3719	gsi = gsi_for_stmt (use_stmt);
3720	gsi_remove (&gsi, true);
3721	release_defs (use_stmt);
3722	use_stmt = gimple_seq_last_stmt (s: stmts);
3723	gsi = gsi_for_stmt (use_nop_stmt);
3724	gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
3725	gimple_assign_set_rhs_with_ops (gsi: &gsi, code: CONVERT_EXPR, op1: var);
3726	update_stmt (s: use_nop_stmt);
3727	}
3728	}
3729	else
3730	return false;
3731
3732	if (!bit)
3733	{
3734	if (ibit < 0)
3735	gcc_unreachable ();
3736	bit = build_int_cst (TREE_TYPE (lhs), ibit);
3737	}
3738	}
3739	else if (optab_handler (op: optab, TYPE_MODE (TREE_TYPE (lhs)))
3740	== CODE_FOR_nothing)
3741	return false;
3742
3743	tree use_lhs = gimple_assign_lhs (gs: use_stmt);
3744	if (!use_lhs)
3745	return false;
3746
3747	if (!bit)
3748	{
3749	if (TREE_CODE (mask) == INTEGER_CST)
3750	{
3751	if (fn == IFN_ATOMIC_BIT_TEST_AND_RESET)
3752	mask = const_unop (BIT_NOT_EXPR, TREE_TYPE (mask), mask);
3753	mask = fold_convert (TREE_TYPE (lhs), mask);
3754	int ibit = tree_log2 (mask);
3755	if (ibit < 0)
3756	return false;
3757	bit = build_int_cst (TREE_TYPE (lhs), ibit);
3758	}
3759	else if (TREE_CODE (mask) == SSA_NAME)
3760	{
3761	gimple *g = SSA_NAME_DEF_STMT (mask);
3762	tree match_op;
3763	if (gimple_nop_convert (mask, &match_op, NULL))
3764	{
3765	mask = match_op;
3766	if (TREE_CODE (mask) != SSA_NAME)
3767	return false;
3768	g = SSA_NAME_DEF_STMT (mask);
3769	}
3770	if (!is_gimple_assign (gs: g))
3771	return false;
3772
3773	if (fn == IFN_ATOMIC_BIT_TEST_AND_RESET)
3774	{
3775	if (gimple_assign_rhs_code (gs: g) != BIT_NOT_EXPR)
3776	return false;
3777	mask = gimple_assign_rhs1 (gs: g);
3778	if (TREE_CODE (mask) != SSA_NAME)
3779	return false;
3780	g = SSA_NAME_DEF_STMT (mask);
3781	}
3782
3783	if (!is_gimple_assign (gs: g)
3784	|| gimple_assign_rhs_code (gs: g) != LSHIFT_EXPR
3785	|| !integer_onep (gimple_assign_rhs1 (gs: g)))
3786	return false;
3787	bit = gimple_assign_rhs2 (gs: g);
3788	}
3789	else
3790	return false;
3791
3792	tree cmp_mask;
3793	if (gimple_assign_rhs1 (gs: use_stmt) == lhs)
3794	cmp_mask = gimple_assign_rhs2 (gs: use_stmt);
3795	else
3796	cmp_mask = gimple_assign_rhs1 (gs: use_stmt);
3797
3798	tree match_op;
3799	if (gimple_nop_convert (cmp_mask, &match_op, NULL))
3800	cmp_mask = match_op;
3801
3802	if (!operand_equal_p (cmp_mask, mask, flags: 0))
3803	return false;
3804	}
3805
3806	bool use_bool = true;
3807	bool has_debug_uses = false;
3808	imm_use_iterator iter;
3809	gimple *g;
3810
3811	if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use_lhs))
3812	use_bool = false;
3813	FOR_EACH_IMM_USE_STMT (g, iter, use_lhs)
3814	{
3815	enum tree_code code = ERROR_MARK;
3816	tree op0 = NULL_TREE, op1 = NULL_TREE;
3817	if (is_gimple_debug (gs: g))
3818	{
3819	has_debug_uses = true;
3820	continue;
3821	}
3822	else if (is_gimple_assign (gs: g))
3823	switch (gimple_assign_rhs_code (gs: g))
3824	{
3825	case COND_EXPR:
3826	op1 = gimple_assign_rhs1 (gs: g);
3827	code = TREE_CODE (op1);
3828	if (TREE_CODE_CLASS (code) != tcc_comparison)
3829	break;
3830	op0 = TREE_OPERAND (op1, 0);
3831	op1 = TREE_OPERAND (op1, 1);
3832	break;
3833	case EQ_EXPR:
3834	case NE_EXPR:
3835	code = gimple_assign_rhs_code (gs: g);
3836	op0 = gimple_assign_rhs1 (gs: g);
3837	op1 = gimple_assign_rhs2 (gs: g);
3838	break;
3839	default:
3840	break;
3841	}
3842	else if (gimple_code (g) == GIMPLE_COND)
3843	{
3844	code = gimple_cond_code (gs: g);
3845	op0 = gimple_cond_lhs (gs: g);
3846	op1 = gimple_cond_rhs (gs: g);
3847	}
3848
3849	if ((code == EQ_EXPR || code == NE_EXPR)
3850	&& op0 == use_lhs
3851	&& integer_zerop (op1))
3852	{
3853	use_operand_p use_p;
3854	int n = 0;
3855	FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3856	n++;
3857	if (n == 1)
3858	continue;
3859	}
3860
3861	use_bool = false;
3862	break;
3863	}
3864
3865	tree new_lhs = make_ssa_name (TREE_TYPE (lhs));
3866	tree flag = build_int_cst (TREE_TYPE (lhs), use_bool);
3867	if (has_model_arg)
3868	g = gimple_build_call_internal (fn, 5, gimple_call_arg (gs: call, index: 0),
3869	bit, flag, gimple_call_arg (gs: call, index: 2),
3870	gimple_call_fn (gs: call));
3871	else
3872	g = gimple_build_call_internal (fn, 4, gimple_call_arg (gs: call, index: 0),
3873	bit, flag, gimple_call_fn (gs: call));
3874	gimple_call_set_lhs (gs: g, lhs: new_lhs);
3875	gimple_set_location (g, location: gimple_location (g: call));
3876	gimple_move_vops (g, call);
3877	bool throws = stmt_can_throw_internal (cfun, call);
3878	gimple_call_set_nothrow (s: as_a <gcall *> (p: g),
3879	nothrow_p: gimple_call_nothrow_p (s: as_a <gcall *> (p: call)));
3880	gimple_stmt_iterator gsi = *gsip;
3881	gsi_insert_after (&gsi, g, GSI_NEW_STMT);
3882	edge e = NULL;
3883	if (throws)
3884	{
3885	maybe_clean_or_replace_eh_stmt (call, g);
3886	if (after || (use_bool && has_debug_uses))
3887	e = find_fallthru_edge (edges: gsi_bb (i: gsi)->succs);
3888	}
3889	if (after)
3890	{
3891	/* The internal function returns the value of the specified bit
3892	before the atomic operation. If we are interested in the value
3893	of the specified bit after the atomic operation (makes only sense
3894	for xor, otherwise the bit content is compile time known),
3895	we need to invert the bit. */
3896	tree mask_convert = mask;
3897	gimple_seq stmts = NULL;
3898	if (!use_bool)
3899	mask_convert = gimple_convert (seq: &stmts, TREE_TYPE (lhs), op: mask);
3900	new_lhs = gimple_build (seq: &stmts, code: BIT_XOR_EXPR, TREE_TYPE (lhs), ops: new_lhs,
3901	ops: use_bool ? build_int_cst (TREE_TYPE (lhs), 1)
3902	: mask_convert);
3903	if (throws)
3904	{
3905	gsi_insert_seq_on_edge_immediate (e, stmts);
3906	gsi = gsi_for_stmt (gimple_seq_last (s: stmts));
3907	}
3908	else
3909	gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
3910	}
3911	if (use_bool && has_debug_uses)
3912	{
3913	tree temp = NULL_TREE;
3914	if (!throws || after || single_pred_p (bb: e->dest))
3915	{
3916	temp = build_debug_expr_decl (TREE_TYPE (lhs));
3917	tree t = build2 (LSHIFT_EXPR, TREE_TYPE (lhs), new_lhs, bit);
3918	g = gimple_build_debug_bind (temp, t, g);
3919	if (throws && !after)
3920	{
3921	gsi = gsi_after_labels (bb: e->dest);
3922	gsi_insert_before (&gsi, g, GSI_SAME_STMT);
3923	}
3924	else
3925	gsi_insert_after (&gsi, g, GSI_NEW_STMT);
3926	}
3927	FOR_EACH_IMM_USE_STMT (g, iter, use_lhs)
3928	if (is_gimple_debug (gs: g))
3929	{
3930	use_operand_p use_p;
3931	if (temp == NULL_TREE)
3932	gimple_debug_bind_reset_value (dbg: g);
3933	else
3934	FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3935	SET_USE (use_p, temp);
3936	update_stmt (s: g);
3937	}
3938	}
3939	SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_lhs)
3940	= SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use_lhs);
3941	replace_uses_by (use_lhs, new_lhs);
3942	gsi = gsi_for_stmt (use_stmt);
3943	gsi_remove (&gsi, true);
3944	release_defs (use_stmt);
3945	gsi_remove (gsip, true);
3946	release_ssa_name (name: lhs);
3947	return true;
3948	}
3949
3950	/* Optimize
3951	_4 = __atomic_add_fetch_* (ptr_6, arg_2, _3);
3952	_5 = _4 == 0;
3953	to
3954	_4 = .ATOMIC_ADD_FETCH_CMP_0 (EQ_EXPR, ptr_6, arg_2, _3);
3955	_5 = _4;
3956	Similarly for __sync_add_and_fetch_* (without the ", _3" part
3957	in there). */
3958
3959	static bool
3960	optimize_atomic_op_fetch_cmp_0 (gimple_stmt_iterator *gsip,
3961	enum internal_fn fn, bool has_model_arg)
3962	{
3963	gimple *call = gsi_stmt (i: *gsip);
3964	tree lhs = gimple_call_lhs (gs: call);
3965	use_operand_p use_p;
3966	gimple *use_stmt;
3967
3968	if (!flag_inline_atomics
3969	|| optimize_debug
3970	|| !gimple_call_builtin_p (call, BUILT_IN_NORMAL)
3971	|| !lhs
3972	|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
3973	|| !single_imm_use (var: lhs, use_p: &use_p, stmt: &use_stmt)
3974	|| !gimple_vdef (g: call))
3975	return false;
3976
3977	optab optab;
3978	switch (fn)
3979	{
3980	case IFN_ATOMIC_ADD_FETCH_CMP_0:
3981	optab = atomic_add_fetch_cmp_0_optab;
3982	break;
3983	case IFN_ATOMIC_SUB_FETCH_CMP_0:
3984	optab = atomic_sub_fetch_cmp_0_optab;
3985	break;
3986	case IFN_ATOMIC_AND_FETCH_CMP_0:
3987	optab = atomic_and_fetch_cmp_0_optab;
3988	break;
3989	case IFN_ATOMIC_OR_FETCH_CMP_0:
3990	optab = atomic_or_fetch_cmp_0_optab;
3991	break;
3992	case IFN_ATOMIC_XOR_FETCH_CMP_0:
3993	optab = atomic_xor_fetch_cmp_0_optab;
3994	break;
3995	default:
3996	return false;
3997	}
3998
3999	if (optab_handler (op: optab, TYPE_MODE (TREE_TYPE (lhs)))
4000	== CODE_FOR_nothing)
4001	return false;
4002
4003	tree use_lhs = lhs;
4004	if (gimple_assign_cast_p (s: use_stmt))
4005	{
4006	use_lhs = gimple_assign_lhs (gs: use_stmt);
4007	if (!tree_nop_conversion_p (TREE_TYPE (use_lhs), TREE_TYPE (lhs))
4008	|| (!INTEGRAL_TYPE_P (TREE_TYPE (use_lhs))
4009	&& !POINTER_TYPE_P (TREE_TYPE (use_lhs)))
4010	|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use_lhs)
4011	|| !single_imm_use (var: use_lhs, use_p: &use_p, stmt: &use_stmt))
4012	return false;
4013	}
4014	enum tree_code code = ERROR_MARK;
4015	tree op0 = NULL_TREE, op1 = NULL_TREE;
4016	if (is_gimple_assign (gs: use_stmt))
4017	switch (gimple_assign_rhs_code (gs: use_stmt))
4018	{
4019	case COND_EXPR:
4020	op1 = gimple_assign_rhs1 (gs: use_stmt);
4021	code = TREE_CODE (op1);
4022	if (TREE_CODE_CLASS (code) == tcc_comparison)
4023	{
4024	op0 = TREE_OPERAND (op1, 0);
4025	op1 = TREE_OPERAND (op1, 1);
4026	}
4027	break;
4028	default:
4029	code = gimple_assign_rhs_code (gs: use_stmt);
4030	if (TREE_CODE_CLASS (code) == tcc_comparison)
4031	{
4032	op0 = gimple_assign_rhs1 (gs: use_stmt);
4033	op1 = gimple_assign_rhs2 (gs: use_stmt);
4034	}
4035	break;
4036	}
4037	else if (gimple_code (g: use_stmt) == GIMPLE_COND)
4038	{
4039	code = gimple_cond_code (gs: use_stmt);
4040	op0 = gimple_cond_lhs (gs: use_stmt);
4041	op1 = gimple_cond_rhs (gs: use_stmt);
4042	}
4043
4044	switch (code)
4045	{
4046	case LT_EXPR:
4047	case LE_EXPR:
4048	case GT_EXPR:
4049	case GE_EXPR:
4050	if (!INTEGRAL_TYPE_P (TREE_TYPE (use_lhs))
4051	|| TREE_CODE (TREE_TYPE (use_lhs)) == BOOLEAN_TYPE
4052	|| TYPE_UNSIGNED (TREE_TYPE (use_lhs)))
4053	return false;
4054	/* FALLTHRU */
4055	case EQ_EXPR:
4056	case NE_EXPR:
4057	if (op0 == use_lhs && integer_zerop (op1))
4058	break;
4059	return false;
4060	default:
4061	return false;
4062	}
4063
4064	int encoded;
4065	switch (code)
4066	{
4067	/* Use special encoding of the operation. We want to also
4068	encode the mode in the first argument and for neither EQ_EXPR
4069	etc. nor EQ etc. we can rely it will fit into QImode. */
4070	case EQ_EXPR: encoded = ATOMIC_OP_FETCH_CMP_0_EQ; break;
4071	case NE_EXPR: encoded = ATOMIC_OP_FETCH_CMP_0_NE; break;
4072	case LT_EXPR: encoded = ATOMIC_OP_FETCH_CMP_0_LT; break;
4073	case LE_EXPR: encoded = ATOMIC_OP_FETCH_CMP_0_LE; break;
4074	case GT_EXPR: encoded = ATOMIC_OP_FETCH_CMP_0_GT; break;
4075	case GE_EXPR: encoded = ATOMIC_OP_FETCH_CMP_0_GE; break;
4076	default: gcc_unreachable ();
4077	}
4078
4079	tree new_lhs = make_ssa_name (boolean_type_node);
4080	gimple *g;
4081	tree flag = build_int_cst (TREE_TYPE (lhs), encoded);
4082	if (has_model_arg)
4083	g = gimple_build_call_internal (fn, 5, flag,
4084	gimple_call_arg (gs: call, index: 0),
4085	gimple_call_arg (gs: call, index: 1),
4086	gimple_call_arg (gs: call, index: 2),
4087	gimple_call_fn (gs: call));
4088	else
4089	g = gimple_build_call_internal (fn, 4, flag,
4090	gimple_call_arg (gs: call, index: 0),
4091	gimple_call_arg (gs: call, index: 1),
4092	gimple_call_fn (gs: call));
4093	gimple_call_set_lhs (gs: g, lhs: new_lhs);
4094	gimple_set_location (g, location: gimple_location (g: call));
4095	gimple_move_vops (g, call);
4096	bool throws = stmt_can_throw_internal (cfun, call);
4097	gimple_call_set_nothrow (s: as_a <gcall *> (p: g),
4098	nothrow_p: gimple_call_nothrow_p (s: as_a <gcall *> (p: call)));
4099	gimple_stmt_iterator gsi = *gsip;
4100	gsi_insert_after (&gsi, g, GSI_SAME_STMT);
4101	if (throws)
4102	maybe_clean_or_replace_eh_stmt (call, g);
4103	if (is_gimple_assign (gs: use_stmt))
4104	switch (gimple_assign_rhs_code (gs: use_stmt))
4105	{
4106	case COND_EXPR:
4107	gimple_assign_set_rhs1 (gs: use_stmt, rhs: new_lhs);
4108	break;
4109	default:
4110	gsi = gsi_for_stmt (use_stmt);
4111	if (tree ulhs = gimple_assign_lhs (gs: use_stmt))
4112	if (useless_type_conversion_p (TREE_TYPE (ulhs),
4113	boolean_type_node))
4114	{
4115	gimple_assign_set_rhs_with_ops (gsi: &gsi, code: SSA_NAME, op1: new_lhs);
4116	break;
4117	}
4118	gimple_assign_set_rhs_with_ops (gsi: &gsi, code: NOP_EXPR, op1: new_lhs);
4119	break;
4120	}
4121	else if (gimple_code (g: use_stmt) == GIMPLE_COND)
4122	{
4123	gcond *use_cond = as_a <gcond *> (p: use_stmt);
4124	gimple_cond_set_code (gs: use_cond, code: NE_EXPR);
4125	gimple_cond_set_lhs (gs: use_cond, lhs: new_lhs);
4126	gimple_cond_set_rhs (gs: use_cond, boolean_false_node);
4127	}
4128
4129	update_stmt (s: use_stmt);
4130	if (use_lhs != lhs)
4131	{
4132	gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (use_lhs));
4133	gsi_remove (&gsi, true);
4134	release_ssa_name (name: use_lhs);
4135	}
4136	gsi_remove (gsip, true);
4137	release_ssa_name (name: lhs);
4138	return true;
4139	}
4140
4141	/* Optimize
4142	a = {};
4143	b = a;
4144	into
4145	a = {};
4146	b = {};
4147	Similarly for memset (&a, ..., sizeof (a)); instead of a = {};
4148	and/or memcpy (&b, &a, sizeof (a)); instead of b = a; */
4149
4150	static void
4151	optimize_memcpy (gimple_stmt_iterator *gsip, tree dest, tree src, tree len)
4152	{
4153	gimple *stmt = gsi_stmt (i: *gsip);
4154	if (gimple_has_volatile_ops (stmt))
4155	return;
4156
4157	tree vuse = gimple_vuse (g: stmt);
4158	if (vuse == NULL)
4159	return;
4160
4161	gimple *defstmt = SSA_NAME_DEF_STMT (vuse);
4162	tree src2 = NULL_TREE, len2 = NULL_TREE;
4163	poly_int64 offset, offset2;
4164	tree val = integer_zero_node;
4165	if (gimple_store_p (gs: defstmt)
4166	&& gimple_assign_single_p (gs: defstmt)
4167	&& TREE_CODE (gimple_assign_rhs1 (defstmt)) == CONSTRUCTOR
4168	&& !gimple_clobber_p (s: defstmt))
4169	src2 = gimple_assign_lhs (gs: defstmt);
4170	else if (gimple_call_builtin_p (defstmt, BUILT_IN_MEMSET)
4171	&& TREE_CODE (gimple_call_arg (defstmt, 0)) == ADDR_EXPR
4172	&& TREE_CODE (gimple_call_arg (defstmt, 1)) == INTEGER_CST)
4173	{
4174	src2 = TREE_OPERAND (gimple_call_arg (defstmt, 0), 0);
4175	len2 = gimple_call_arg (gs: defstmt, index: 2);
4176	val = gimple_call_arg (gs: defstmt, index: 1);
4177	/* For non-0 val, we'd have to transform stmt from assignment
4178	into memset (only if dest is addressable). */
4179	if (!integer_zerop (val) && is_gimple_assign (gs: stmt))
4180	src2 = NULL_TREE;
4181	}
4182
4183	if (src2 == NULL_TREE)
4184	return;
4185
4186	if (len == NULL_TREE)
4187	len = (TREE_CODE (src) == COMPONENT_REF
4188	? DECL_SIZE_UNIT (TREE_OPERAND (src, 1))
4189	: TYPE_SIZE_UNIT (TREE_TYPE (src)));
4190	if (len2 == NULL_TREE)
4191	len2 = (TREE_CODE (src2) == COMPONENT_REF
4192	? DECL_SIZE_UNIT (TREE_OPERAND (src2, 1))
4193	: TYPE_SIZE_UNIT (TREE_TYPE (src2)));
4194	if (len == NULL_TREE
4195	|| !poly_int_tree_p (t: len)
4196	|| len2 == NULL_TREE
4197	|| !poly_int_tree_p (t: len2))
4198	return;
4199
4200	src = get_addr_base_and_unit_offset (src, &offset);
4201	src2 = get_addr_base_and_unit_offset (src2, &offset2);
4202	if (src == NULL_TREE
4203	|| src2 == NULL_TREE
4204	|| maybe_lt (a: offset, b: offset2))
4205	return;
4206
4207	if (!operand_equal_p (src, src2, flags: 0))
4208	return;
4209
4210	/* [ src + offset2, src + offset2 + len2 - 1 ] is set to val.
4211	Make sure that
4212	[ src + offset, src + offset + len - 1 ] is a subset of that. */
4213	if (maybe_gt (wi::to_poly_offset (len) + (offset - offset2),
4214	wi::to_poly_offset (len2)))
4215	return;
4216
4217	if (dump_file && (dump_flags & TDF_DETAILS))
4218	{
4219	fprintf (stream: dump_file, format: "Simplified\n ");
4220	print_gimple_stmt (dump_file, stmt, 0, dump_flags);
4221	fprintf (stream: dump_file, format: "after previous\n ");
4222	print_gimple_stmt (dump_file, defstmt, 0, dump_flags);
4223	}
4224
4225	/* For simplicity, don't change the kind of the stmt,
4226	turn dest = src; into dest = {}; and memcpy (&dest, &src, len);
4227	into memset (&dest, val, len);
4228	In theory we could change dest = src into memset if dest
4229	is addressable (maybe beneficial if val is not 0), or
4230	memcpy (&dest, &src, len) into dest = {} if len is the size
4231	of dest, dest isn't volatile. */
4232	if (is_gimple_assign (gs: stmt))
4233	{
4234	tree ctor = build_constructor (TREE_TYPE (dest), NULL);
4235	gimple_assign_set_rhs_from_tree (gsip, ctor);
4236	update_stmt (s: stmt);
4237	}
4238	else /* If stmt is memcpy, transform it into memset. */
4239	{
4240	gcall *call = as_a <gcall *> (p: stmt);
4241	tree fndecl = builtin_decl_implicit (fncode: BUILT_IN_MEMSET);
4242	gimple_call_set_fndecl (gs: call, decl: fndecl);
4243	gimple_call_set_fntype (call_stmt: call, TREE_TYPE (fndecl));
4244	gimple_call_set_arg (gs: call, index: 1, arg: val);
4245	update_stmt (s: stmt);
4246	}
4247
4248	if (dump_file && (dump_flags & TDF_DETAILS))
4249	{
4250	fprintf (stream: dump_file, format: "into\n ");
4251	print_gimple_stmt (dump_file, stmt, 0, dump_flags);
4252	}
4253	}
4254
4255	/* A simple pass that attempts to fold all builtin functions. This pass
4256	is run after we've propagated as many constants as we can. */
4257
4258	namespace {
4259
4260	const pass_data pass_data_fold_builtins =
4261	{
4262	.type: GIMPLE_PASS, /* type */
4263	.name: "fab", /* name */
4264	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
4265	.tv_id: TV_NONE, /* tv_id */
4266	.properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
4267	.properties_provided: 0, /* properties_provided */
4268	.properties_destroyed: 0, /* properties_destroyed */
4269	.todo_flags_start: 0, /* todo_flags_start */
4270	TODO_update_ssa, /* todo_flags_finish */
4271	};
4272
4273	class pass_fold_builtins : public gimple_opt_pass
4274	{
4275	public:
4276	pass_fold_builtins (gcc::context *ctxt)
4277	: gimple_opt_pass (pass_data_fold_builtins, ctxt)
4278	{}
4279
4280	/* opt_pass methods: */
4281	opt_pass * clone () final override { return new pass_fold_builtins (m_ctxt); }
4282	unsigned int execute (function *) final override;
4283
4284	}; // class pass_fold_builtins
4285
4286	unsigned int
4287	pass_fold_builtins::execute (function *fun)
4288	{
4289	bool cfg_changed = false;
4290	basic_block bb;
4291	unsigned int todoflags = 0;
4292
4293	FOR_EACH_BB_FN (bb, fun)
4294	{
4295	gimple_stmt_iterator i;
4296	for (i = gsi_start_bb (bb); !gsi_end_p (i); )
4297	{
4298	gimple *stmt, *old_stmt;
4299	tree callee;
4300	enum built_in_function fcode;
4301
4302	stmt = gsi_stmt (i);
4303
4304	if (gimple_code (g: stmt) != GIMPLE_CALL)
4305	{
4306	if (gimple_assign_load_p (stmt) && gimple_store_p (gs: stmt))
4307	optimize_memcpy (gsip: &i, dest: gimple_assign_lhs (gs: stmt),
4308	src: gimple_assign_rhs1 (gs: stmt), NULL_TREE);
4309	gsi_next (i: &i);
4310	continue;
4311	}
4312
4313	callee = gimple_call_fndecl (gs: stmt);
4314	if (!callee
4315	&& gimple_call_internal_p (gs: stmt, fn: IFN_ASSUME))
4316	{
4317	gsi_remove (&i, true);
4318	continue;
4319	}
4320	if (!callee || !fndecl_built_in_p (node: callee, klass: BUILT_IN_NORMAL))
4321	{
4322	gsi_next (i: &i);
4323	continue;
4324	}
4325
4326	fcode = DECL_FUNCTION_CODE (decl: callee);
4327	if (fold_stmt (&i))
4328	;
4329	else
4330	{
4331	tree result = NULL_TREE;
4332	switch (DECL_FUNCTION_CODE (decl: callee))
4333	{
4334	case BUILT_IN_CONSTANT_P:
4335	/* Resolve __builtin_constant_p. If it hasn't been
4336	folded to integer_one_node by now, it's fairly
4337	certain that the value simply isn't constant. */
4338	result = integer_zero_node;
4339	break;
4340
4341	case BUILT_IN_ASSUME_ALIGNED:
4342	/* Remove __builtin_assume_aligned. */
4343	result = gimple_call_arg (gs: stmt, index: 0);
4344	break;
4345
4346	case BUILT_IN_STACK_RESTORE:
4347	result = optimize_stack_restore (i);
4348	if (result)
4349	break;
4350	gsi_next (i: &i);
4351	continue;
4352
4353	case BUILT_IN_UNREACHABLE:
4354	if (optimize_unreachable (i))
4355	cfg_changed = true;
4356	break;
4357
4358	case BUILT_IN_ATOMIC_ADD_FETCH_1:
4359	case BUILT_IN_ATOMIC_ADD_FETCH_2:
4360	case BUILT_IN_ATOMIC_ADD_FETCH_4:
4361	case BUILT_IN_ATOMIC_ADD_FETCH_8:
4362	case BUILT_IN_ATOMIC_ADD_FETCH_16:
4363	optimize_atomic_op_fetch_cmp_0 (gsip: &i,
4364	fn: IFN_ATOMIC_ADD_FETCH_CMP_0,
4365	has_model_arg: true);
4366	break;
4367	case BUILT_IN_SYNC_ADD_AND_FETCH_1:
4368	case BUILT_IN_SYNC_ADD_AND_FETCH_2:
4369	case BUILT_IN_SYNC_ADD_AND_FETCH_4:
4370	case BUILT_IN_SYNC_ADD_AND_FETCH_8:
4371	case BUILT_IN_SYNC_ADD_AND_FETCH_16:
4372	optimize_atomic_op_fetch_cmp_0 (gsip: &i,
4373	fn: IFN_ATOMIC_ADD_FETCH_CMP_0,
4374	has_model_arg: false);
4375	break;
4376
4377	case BUILT_IN_ATOMIC_SUB_FETCH_1:
4378	case BUILT_IN_ATOMIC_SUB_FETCH_2:
4379	case BUILT_IN_ATOMIC_SUB_FETCH_4:
4380	case BUILT_IN_ATOMIC_SUB_FETCH_8:
4381	case BUILT_IN_ATOMIC_SUB_FETCH_16:
4382	optimize_atomic_op_fetch_cmp_0 (gsip: &i,
4383	fn: IFN_ATOMIC_SUB_FETCH_CMP_0,
4384	has_model_arg: true);
4385	break;
4386	case BUILT_IN_SYNC_SUB_AND_FETCH_1:
4387	case BUILT_IN_SYNC_SUB_AND_FETCH_2:
4388	case BUILT_IN_SYNC_SUB_AND_FETCH_4:
4389	case BUILT_IN_SYNC_SUB_AND_FETCH_8:
4390	case BUILT_IN_SYNC_SUB_AND_FETCH_16:
4391	optimize_atomic_op_fetch_cmp_0 (gsip: &i,
4392	fn: IFN_ATOMIC_SUB_FETCH_CMP_0,
4393	has_model_arg: false);
4394	break;
4395
4396	case BUILT_IN_ATOMIC_FETCH_OR_1:
4397	case BUILT_IN_ATOMIC_FETCH_OR_2:
4398	case BUILT_IN_ATOMIC_FETCH_OR_4:
4399	case BUILT_IN_ATOMIC_FETCH_OR_8:
4400	case BUILT_IN_ATOMIC_FETCH_OR_16:
4401	optimize_atomic_bit_test_and (gsip: &i,
4402	fn: IFN_ATOMIC_BIT_TEST_AND_SET,
4403	has_model_arg: true, after: false);
4404	break;
4405	case BUILT_IN_SYNC_FETCH_AND_OR_1:
4406	case BUILT_IN_SYNC_FETCH_AND_OR_2:
4407	case BUILT_IN_SYNC_FETCH_AND_OR_4:
4408	case BUILT_IN_SYNC_FETCH_AND_OR_8:
4409	case BUILT_IN_SYNC_FETCH_AND_OR_16:
4410	optimize_atomic_bit_test_and (gsip: &i,
4411	fn: IFN_ATOMIC_BIT_TEST_AND_SET,
4412	has_model_arg: false, after: false);
4413	break;
4414
4415	case BUILT_IN_ATOMIC_FETCH_XOR_1:
4416	case BUILT_IN_ATOMIC_FETCH_XOR_2:
4417	case BUILT_IN_ATOMIC_FETCH_XOR_4:
4418	case BUILT_IN_ATOMIC_FETCH_XOR_8:
4419	case BUILT_IN_ATOMIC_FETCH_XOR_16:
4420	optimize_atomic_bit_test_and
4421	(gsip: &i, fn: IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT, has_model_arg: true, after: false);
4422	break;
4423	case BUILT_IN_SYNC_FETCH_AND_XOR_1:
4424	case BUILT_IN_SYNC_FETCH_AND_XOR_2:
4425	case BUILT_IN_SYNC_FETCH_AND_XOR_4:
4426	case BUILT_IN_SYNC_FETCH_AND_XOR_8:
4427	case BUILT_IN_SYNC_FETCH_AND_XOR_16:
4428	optimize_atomic_bit_test_and
4429	(gsip: &i, fn: IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT, has_model_arg: false, after: false);
4430	break;
4431
4432	case BUILT_IN_ATOMIC_XOR_FETCH_1:
4433	case BUILT_IN_ATOMIC_XOR_FETCH_2:
4434	case BUILT_IN_ATOMIC_XOR_FETCH_4:
4435	case BUILT_IN_ATOMIC_XOR_FETCH_8:
4436	case BUILT_IN_ATOMIC_XOR_FETCH_16:
4437	if (optimize_atomic_bit_test_and
4438	(gsip: &i, fn: IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT, has_model_arg: true, after: true))
4439	break;
4440	optimize_atomic_op_fetch_cmp_0 (gsip: &i,
4441	fn: IFN_ATOMIC_XOR_FETCH_CMP_0,
4442	has_model_arg: true);
4443	break;
4444	case BUILT_IN_SYNC_XOR_AND_FETCH_1:
4445	case BUILT_IN_SYNC_XOR_AND_FETCH_2:
4446	case BUILT_IN_SYNC_XOR_AND_FETCH_4:
4447	case BUILT_IN_SYNC_XOR_AND_FETCH_8:
4448	case BUILT_IN_SYNC_XOR_AND_FETCH_16:
4449	if (optimize_atomic_bit_test_and
4450	(gsip: &i, fn: IFN_ATOMIC_BIT_TEST_AND_COMPLEMENT, has_model_arg: false, after: true))
4451	break;
4452	optimize_atomic_op_fetch_cmp_0 (gsip: &i,
4453	fn: IFN_ATOMIC_XOR_FETCH_CMP_0,
4454	has_model_arg: false);
4455	break;
4456
4457	case BUILT_IN_ATOMIC_FETCH_AND_1:
4458	case BUILT_IN_ATOMIC_FETCH_AND_2:
4459	case BUILT_IN_ATOMIC_FETCH_AND_4:
4460	case BUILT_IN_ATOMIC_FETCH_AND_8:
4461	case BUILT_IN_ATOMIC_FETCH_AND_16:
4462	optimize_atomic_bit_test_and (gsip: &i,
4463	fn: IFN_ATOMIC_BIT_TEST_AND_RESET,
4464	has_model_arg: true, after: false);
4465	break;
4466	case BUILT_IN_SYNC_FETCH_AND_AND_1:
4467	case BUILT_IN_SYNC_FETCH_AND_AND_2:
4468	case BUILT_IN_SYNC_FETCH_AND_AND_4:
4469	case BUILT_IN_SYNC_FETCH_AND_AND_8:
4470	case BUILT_IN_SYNC_FETCH_AND_AND_16:
4471	optimize_atomic_bit_test_and (gsip: &i,
4472	fn: IFN_ATOMIC_BIT_TEST_AND_RESET,
4473	has_model_arg: false, after: false);
4474	break;
4475
4476	case BUILT_IN_ATOMIC_AND_FETCH_1:
4477	case BUILT_IN_ATOMIC_AND_FETCH_2:
4478	case BUILT_IN_ATOMIC_AND_FETCH_4:
4479	case BUILT_IN_ATOMIC_AND_FETCH_8:
4480	case BUILT_IN_ATOMIC_AND_FETCH_16:
4481	optimize_atomic_op_fetch_cmp_0 (gsip: &i,
4482	fn: IFN_ATOMIC_AND_FETCH_CMP_0,
4483	has_model_arg: true);
4484	break;
4485	case BUILT_IN_SYNC_AND_AND_FETCH_1:
4486	case BUILT_IN_SYNC_AND_AND_FETCH_2:
4487	case BUILT_IN_SYNC_AND_AND_FETCH_4:
4488	case BUILT_IN_SYNC_AND_AND_FETCH_8:
4489	case BUILT_IN_SYNC_AND_AND_FETCH_16:
4490	optimize_atomic_op_fetch_cmp_0 (gsip: &i,
4491	fn: IFN_ATOMIC_AND_FETCH_CMP_0,
4492	has_model_arg: false);
4493	break;
4494
4495	case BUILT_IN_ATOMIC_OR_FETCH_1:
4496	case BUILT_IN_ATOMIC_OR_FETCH_2:
4497	case BUILT_IN_ATOMIC_OR_FETCH_4:
4498	case BUILT_IN_ATOMIC_OR_FETCH_8:
4499	case BUILT_IN_ATOMIC_OR_FETCH_16:
4500	optimize_atomic_op_fetch_cmp_0 (gsip: &i,
4501	fn: IFN_ATOMIC_OR_FETCH_CMP_0,
4502	has_model_arg: true);
4503	break;
4504	case BUILT_IN_SYNC_OR_AND_FETCH_1:
4505	case BUILT_IN_SYNC_OR_AND_FETCH_2:
4506	case BUILT_IN_SYNC_OR_AND_FETCH_4:
4507	case BUILT_IN_SYNC_OR_AND_FETCH_8:
4508	case BUILT_IN_SYNC_OR_AND_FETCH_16:
4509	optimize_atomic_op_fetch_cmp_0 (gsip: &i,
4510	fn: IFN_ATOMIC_OR_FETCH_CMP_0,
4511	has_model_arg: false);
4512	break;
4513
4514	case BUILT_IN_MEMCPY:
4515	if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)
4516	&& TREE_CODE (gimple_call_arg (stmt, 0)) == ADDR_EXPR
4517	&& TREE_CODE (gimple_call_arg (stmt, 1)) == ADDR_EXPR
4518	&& TREE_CODE (gimple_call_arg (stmt, 2)) == INTEGER_CST)
4519	{
4520	tree dest = TREE_OPERAND (gimple_call_arg (stmt, 0), 0);
4521	tree src = TREE_OPERAND (gimple_call_arg (stmt, 1), 0);
4522	tree len = gimple_call_arg (gs: stmt, index: 2);
4523	optimize_memcpy (gsip: &i, dest, src, len);
4524	}
4525	break;
4526
4527	case BUILT_IN_VA_START:
4528	case BUILT_IN_VA_END:
4529	case BUILT_IN_VA_COPY:
4530	/* These shouldn't be folded before pass_stdarg. */
4531	result = optimize_stdarg_builtin (call: stmt);
4532	break;
4533
4534	default:;
4535	}
4536
4537	if (!result)
4538	{
4539	gsi_next (i: &i);
4540	continue;
4541	}
4542
4543	gimplify_and_update_call_from_tree (&i, result);
4544	}
4545
4546	todoflags |= TODO_update_address_taken;
4547
4548	if (dump_file && (dump_flags & TDF_DETAILS))
4549	{
4550	fprintf (stream: dump_file, format: "Simplified\n ");
4551	print_gimple_stmt (dump_file, stmt, 0, dump_flags);
4552	}
4553
4554	old_stmt = stmt;
4555	stmt = gsi_stmt (i);
4556	update_stmt (s: stmt);
4557
4558	if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)
4559	&& gimple_purge_dead_eh_edges (bb))
4560	cfg_changed = true;
4561
4562	if (dump_file && (dump_flags & TDF_DETAILS))
4563	{
4564	fprintf (stream: dump_file, format: "to\n ");
4565	print_gimple_stmt (dump_file, stmt, 0, dump_flags);
4566	fprintf (stream: dump_file, format: "\n");
4567	}
4568
4569	/* Retry the same statement if it changed into another
4570	builtin, there might be new opportunities now. */
4571	if (gimple_code (g: stmt) != GIMPLE_CALL)
4572	{
4573	gsi_next (i: &i);
4574	continue;
4575	}
4576	callee = gimple_call_fndecl (gs: stmt);
4577	if (!callee
4578	|| !fndecl_built_in_p (node: callee, name1: fcode))
4579	gsi_next (i: &i);
4580	}
4581	}
4582
4583	/* Delete unreachable blocks. */
4584	if (cfg_changed)
4585	todoflags |= TODO_cleanup_cfg;
4586
4587	return todoflags;
4588	}
4589
4590	} // anon namespace
4591
4592	gimple_opt_pass *
4593	make_pass_fold_builtins (gcc::context *ctxt)
4594	{
4595	return new pass_fold_builtins (ctxt);
4596	}
4597
4598	/* A simple pass that emits some warnings post IPA. */
4599
4600	namespace {
4601
4602	const pass_data pass_data_post_ipa_warn =
4603	{
4604	.type: GIMPLE_PASS, /* type */
4605	.name: "post_ipa_warn", /* name */
4606	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
4607	.tv_id: TV_NONE, /* tv_id */
4608	.properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
4609	.properties_provided: 0, /* properties_provided */
4610	.properties_destroyed: 0, /* properties_destroyed */
4611	.todo_flags_start: 0, /* todo_flags_start */
4612	.todo_flags_finish: 0, /* todo_flags_finish */
4613	};
4614
4615	class pass_post_ipa_warn : public gimple_opt_pass
4616	{
4617	public:
4618	pass_post_ipa_warn (gcc::context *ctxt)
4619	: gimple_opt_pass (pass_data_post_ipa_warn, ctxt)
4620	{}
4621
4622	/* opt_pass methods: */
4623	opt_pass * clone () final override { return new pass_post_ipa_warn (m_ctxt); }
4624	bool gate (function *) final override { return warn_nonnull != 0; }
4625	unsigned int execute (function *) final override;
4626
4627	}; // class pass_fold_builtins
4628
4629	unsigned int
4630	pass_post_ipa_warn::execute (function *fun)
4631	{
4632	basic_block bb;
4633
4634	FOR_EACH_BB_FN (bb, fun)
4635	{
4636	gimple_stmt_iterator gsi;
4637	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
4638	{
4639	gimple *stmt = gsi_stmt (i: gsi);
4640	if (!is_gimple_call (gs: stmt) || warning_suppressed_p (stmt, OPT_Wnonnull))
4641	continue;
4642
4643	tree fntype = gimple_call_fntype (gs: stmt);
4644	bitmap nonnullargs = get_nonnull_args (fntype);
4645	if (!nonnullargs)
4646	continue;
4647
4648	tree fndecl = gimple_call_fndecl (gs: stmt);
4649	const bool closure = fndecl && DECL_LAMBDA_FUNCTION_P (fndecl);
4650
4651	for (unsigned i = 0; i < gimple_call_num_args (gs: stmt); i++)
4652	{
4653	tree arg = gimple_call_arg (gs: stmt, index: i);
4654	if (TREE_CODE (TREE_TYPE (arg)) != POINTER_TYPE)
4655	continue;
4656	if (!integer_zerop (arg))
4657	continue;
4658	if (i == 0 && closure)
4659	/* Avoid warning for the first argument to lambda functions. */
4660	continue;
4661	if (!bitmap_empty_p (map: nonnullargs)
4662	&& !bitmap_bit_p (nonnullargs, i))
4663	continue;
4664
4665	/* In C++ non-static member functions argument 0 refers
4666	to the implicit this pointer. Use the same one-based
4667	numbering for ordinary arguments. */
4668	unsigned argno = TREE_CODE (fntype) == METHOD_TYPE ? i : i + 1;
4669	location_t loc = (EXPR_HAS_LOCATION (arg)
4670	? EXPR_LOCATION (arg)
4671	: gimple_location (g: stmt));
4672	auto_diagnostic_group d;
4673	if (argno == 0)
4674	{
4675	if (warning_at (loc, OPT_Wnonnull,
4676	"%qs pointer is null", "this")
4677	&& fndecl)
4678	inform (DECL_SOURCE_LOCATION (fndecl),
4679	"in a call to non-static member function %qD",
4680	fndecl);
4681	continue;
4682	}
4683
4684	if (!warning_at (loc, OPT_Wnonnull,
4685	"argument %u null where non-null "
4686	"expected", argno))
4687	continue;
4688
4689	tree fndecl = gimple_call_fndecl (gs: stmt);
4690	if (fndecl && DECL_IS_UNDECLARED_BUILTIN (fndecl))
4691	inform (loc, "in a call to built-in function %qD",
4692	fndecl);
4693	else if (fndecl)
4694	inform (DECL_SOURCE_LOCATION (fndecl),
4695	"in a call to function %qD declared %qs",
4696	fndecl, "nonnull");
4697	}
4698	BITMAP_FREE (nonnullargs);
4699	}
4700	}
4701	return 0;
4702	}
4703
4704	} // anon namespace
4705
4706	gimple_opt_pass *
4707	make_pass_post_ipa_warn (gcc::context *ctxt)
4708	{
4709	return new pass_post_ipa_warn (ctxt);
4710	}
4711