1	/* Support for simple predicate analysis.
2
3	Copyright (C) 2001-2024 Free Software Foundation, Inc.
4	Contributed by Xinliang David Li <davidxl@google.com>
5	Generalized by Martin Sebor <msebor@redhat.com>
6
7	This file is part of GCC.
8
9	GCC is free software; you can redistribute it and/or modify
10	it under the terms of the GNU General Public License as published by
11	the Free Software Foundation; either version 3, or (at your option)
12	any later version.
13
14	GCC is distributed in the hope that it will be useful,
15	but WITHOUT ANY WARRANTY; without even the implied warranty of
16	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17	GNU General Public License for more details.
18
19	You should have received a copy of the GNU General Public License
20	along with GCC; see the file COPYING3. If not see
21	<http://www.gnu.org/licenses/>. */
22
23	#define INCLUDE_STRING
24	#include "config.h"
25	#include "system.h"
26	#include "coretypes.h"
27	#include "backend.h"
28	#include "tree.h"
29	#include "gimple.h"
30	#include "tree-pass.h"
31	#include "ssa.h"
32	#include "gimple-pretty-print.h"
33	#include "diagnostic-core.h"
34	#include "fold-const.h"
35	#include "gimple-iterator.h"
36	#include "tree-ssa.h"
37	#include "tree-cfg.h"
38	#include "cfghooks.h"
39	#include "attribs.h"
40	#include "builtins.h"
41	#include "calls.h"
42	#include "value-query.h"
43	#include "cfganal.h"
44	#include "tree-eh.h"
45	#include "gimple-fold.h"
46
47	#include "gimple-predicate-analysis.h"
48
49	#define DEBUG_PREDICATE_ANALYZER 1
50
51	/* In our predicate normal form we have MAX_NUM_CHAINS or predicates
52	and in those MAX_CHAIN_LEN (inverted) and predicates. */
53	#define MAX_NUM_CHAINS (unsigned)param_uninit_max_num_chains
54	#define MAX_CHAIN_LEN (unsigned)param_uninit_max_chain_len
55
56	/* Return true if X1 is the negation of X2. */
57
58	static inline bool
59	pred_neg_p (const pred_info &x1, const pred_info &x2)
60	{
61	if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, flags: 0)
62	|| !operand_equal_p (x1.pred_rhs, x2.pred_rhs, flags: 0))
63	return false;
64
65	tree_code c1 = x1.cond_code, c2;
66	if (x1.invert == x2.invert)
67	c2 = invert_tree_comparison (x2.cond_code, false);
68	else
69	c2 = x2.cond_code;
70
71	return c1 == c2;
72	}
73
74	/* Return whether the condition (VAL CMPC BOUNDARY) is true. */
75
76	static bool
77	is_value_included_in (tree val, tree boundary, tree_code cmpc)
78	{
79	/* Only handle integer constant here. */
80	if (TREE_CODE (val) != INTEGER_CST || TREE_CODE (boundary) != INTEGER_CST)
81	return true;
82
83	bool inverted = false;
84	if (cmpc == GE_EXPR || cmpc == GT_EXPR || cmpc == NE_EXPR)
85	{
86	cmpc = invert_tree_comparison (cmpc, false);
87	inverted = true;
88	}
89
90	bool result;
91	if (cmpc == EQ_EXPR)
92	result = tree_int_cst_equal (val, boundary);
93	else if (cmpc == LT_EXPR)
94	result = tree_int_cst_lt (t1: val, t2: boundary);
95	else
96	{
97	gcc_assert (cmpc == LE_EXPR);
98	result = tree_int_cst_le (t1: val, t2: boundary);
99	}
100
101	if (inverted)
102	result ^= 1;
103
104	return result;
105	}
106
107	/* Format the vector of edges EV as a string. */
108
109	static std::string
110	format_edge_vec (const vec<edge> &ev)
111	{
112	std::string str;
113
114	unsigned n = ev.length ();
115	for (unsigned i = 0; i < n; ++i)
116	{
117	char es[32];
118	const_edge e = ev[i];
119	sprintf (s: es, format: "%u -> %u", e->src->index, e->dest->index);
120	str += es;
121	if (i + 1 < n)
122	str += ", ";
123	}
124	return str;
125	}
126
127	/* Format the first N elements of the array of vector of edges EVA as
128	a string. */
129
130	static std::string
131	format_edge_vecs (const vec<edge> eva[], unsigned n)
132	{
133	std::string str;
134
135	for (unsigned i = 0; i != n; ++i)
136	{
137	str += '{';
138	str += format_edge_vec (ev: eva[i]);
139	str += '}';
140	if (i + 1 < n)
141	str += ", ";
142	}
143	return str;
144	}
145
146	/* Dump a single pred_info to F. */
147
148	static void
149	dump_pred_info (FILE *f, const pred_info &pred)
150	{
151	if (pred.invert)
152	fprintf (stream: f, format: "NOT (");
153	print_generic_expr (f, pred.pred_lhs);
154	fprintf (stream: f, format: " %s ", op_symbol_code (pred.cond_code));
155	print_generic_expr (f, pred.pred_rhs);
156	if (pred.invert)
157	fputc (c: ')', stream: f);
158	}
159
160	/* Dump a pred_chain to F. */
161
162	static void
163	dump_pred_chain (FILE *f, const pred_chain &chain)
164	{
165	unsigned np = chain.length ();
166	for (unsigned j = 0; j < np; j++)
167	{
168	if (j > 0)
169	fprintf (stream: f, format: " AND (");
170	else
171	fputc (c: '(', stream: f);
172	dump_pred_info (f, pred: chain[j]);
173	fputc (c: ')', stream: f);
174	}
175	}
176
177	/* Return the 'normalized' conditional code with operand swapping
178	and condition inversion controlled by SWAP_COND and INVERT. */
179
180	static tree_code
181	get_cmp_code (tree_code orig_cmp_code, bool swap_cond, bool invert)
182	{
183	tree_code tc = orig_cmp_code;
184
185	if (swap_cond)
186	tc = swap_tree_comparison (orig_cmp_code);
187	if (invert)
188	tc = invert_tree_comparison (tc, false);
189
190	switch (tc)
191	{
192	case LT_EXPR:
193	case LE_EXPR:
194	case GT_EXPR:
195	case GE_EXPR:
196	case EQ_EXPR:
197	case NE_EXPR:
198	break;
199	default:
200	return ERROR_MARK;
201	}
202	return tc;
203	}
204
205	/* Return true if PRED is common among all predicate chains in PREDS
206	(and therefore can be factored out). */
207
208	static bool
209	find_matching_predicate_in_rest_chains (const pred_info &pred,
210	const pred_chain_union &preds)
211	{
212	/* Trival case. */
213	if (preds.length () == 1)
214	return true;
215
216	for (unsigned i = 1; i < preds.length (); i++)
217	{
218	bool found = false;
219	const pred_chain &chain = preds[i];
220	unsigned n = chain.length ();
221	for (unsigned j = 0; j < n; j++)
222	{
223	const pred_info &pred2 = chain[j];
224	/* Can relax the condition comparison to not use address
225	comparison. However, the most common case is that
226	multiple control dependent paths share a common path
227	prefix, so address comparison should be ok. */
228	if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, flags: 0)
229	&& operand_equal_p (pred2.pred_rhs, pred.pred_rhs, flags: 0)
230	&& pred2.invert == pred.invert)
231	{
232	found = true;
233	break;
234	}
235	}
236	if (!found)
237	return false;
238	}
239	return true;
240	}
241
242	/* Find a predicate to examine against paths of interest. If there
243	is no predicate of the "FLAG_VAR CMP CONST" form, try to find one
244	of that's the form "FLAG_VAR CMP FLAG_VAR" with value range info.
245	PHI is the phi node whose incoming (interesting) paths need to be
246	examined. On success, return the comparison code, set defintion
247	gimple of FLAG_DEF and BOUNDARY_CST. Otherwise return ERROR_MARK.
248	I is the running iterator so the function can be called repeatedly
249	to gather all candidates. */
250
251	static tree_code
252	find_var_cmp_const (pred_chain_union preds, gphi *phi, gimple **flag_def,
253	tree *boundary_cst, unsigned &i)
254	{
255	gcc_assert (preds.length () > 0);
256	pred_chain chain = preds[0];
257	for (; i < chain.length (); i++)
258	{
259	const pred_info &pred = chain[i];
260	tree cond_lhs = pred.pred_lhs;
261	tree cond_rhs = pred.pred_rhs;
262	if (cond_lhs == NULL_TREE || cond_rhs == NULL_TREE)
263	continue;
264
265	tree_code code = get_cmp_code (orig_cmp_code: pred.cond_code, swap_cond: false, invert: pred.invert);
266	if (code == ERROR_MARK)
267	continue;
268
269	/* Convert to the canonical form SSA_NAME CMP CONSTANT. */
270	if (TREE_CODE (cond_lhs) == SSA_NAME
271	&& is_gimple_constant (t: cond_rhs))
272	;
273	else if (TREE_CODE (cond_rhs) == SSA_NAME
274	&& is_gimple_constant (t: cond_lhs))
275	{
276	std::swap (a&: cond_lhs, b&: cond_rhs);
277	if ((code = get_cmp_code (orig_cmp_code: code, swap_cond: true, invert: false)) == ERROR_MARK)
278	continue;
279	}
280	/* Check if we can take advantage of FLAG_VAR COMP FLAG_VAR predicate
281	with value range info. Note only first of such case is handled. */
282	else if (TREE_CODE (cond_lhs) == SSA_NAME
283	&& TREE_CODE (cond_rhs) == SSA_NAME)
284	{
285	gimple* lhs_def = SSA_NAME_DEF_STMT (cond_lhs);
286	if (!lhs_def || gimple_code (g: lhs_def) != GIMPLE_PHI
287	|| gimple_bb (g: lhs_def) != gimple_bb (g: phi))
288	{
289	std::swap (a&: cond_lhs, b&: cond_rhs);
290	if ((code = get_cmp_code (orig_cmp_code: code, swap_cond: true, invert: false)) == ERROR_MARK)
291	continue;
292	}
293
294	/* Check value range info of rhs, do following transforms:
295	flag_var < [min, max] -> flag_var < max
296	flag_var > [min, max] -> flag_var > min
297
298	We can also transform LE_EXPR/GE_EXPR to LT_EXPR/GT_EXPR:
299	flag_var <= [min, max] -> flag_var < [min, max+1]
300	flag_var >= [min, max] -> flag_var > [min-1, max]
301	if no overflow/wrap. */
302	tree type = TREE_TYPE (cond_lhs);
303	value_range r;
304	if (!INTEGRAL_TYPE_P (type)
305	|| !get_range_query (cfun)->range_of_expr (r, expr: cond_rhs)
306	|| r.undefined_p ()
307	|| r.varying_p ())
308	continue;
309
310	wide_int min = r.lower_bound ();
311	wide_int max = r.upper_bound ();
312	if (code == LE_EXPR
313	&& max != wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
314	{
315	code = LT_EXPR;
316	max = max + 1;
317	}
318	if (code == GE_EXPR
319	&& min != wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
320	{
321	code = GT_EXPR;
322	min = min - 1;
323	}
324	if (code == LT_EXPR)
325	cond_rhs = wide_int_to_tree (type, cst: max);
326	else if (code == GT_EXPR)
327	cond_rhs = wide_int_to_tree (type, cst: min);
328	else
329	continue;
330	}
331	else
332	continue;
333
334	if ((*flag_def = SSA_NAME_DEF_STMT (cond_lhs)) == NULL)
335	continue;
336
337	if (gimple_code (g: *flag_def) != GIMPLE_PHI
338	|| gimple_bb (g: *flag_def) != gimple_bb (g: phi)
339	|| !find_matching_predicate_in_rest_chains (pred, preds))
340	continue;
341
342	/* Return predicate found. */
343	*boundary_cst = cond_rhs;
344	++i;
345	return code;
346	}
347
348	return ERROR_MARK;
349	}
350
351	/* Return true if all interesting opnds are pruned, false otherwise.
352	PHI is the phi node with interesting operands, OPNDS is the bitmap
353	of the interesting operand positions, FLAG_DEF is the statement
354	defining the flag guarding the use of the PHI output, BOUNDARY_CST
355	is the const value used in the predicate associated with the flag,
356	CMP_CODE is the comparison code used in the predicate, VISITED_PHIS
357	is the pointer set of phis visited, and VISITED_FLAG_PHIS is
358	the pointer to the pointer set of flag definitions that are also
359	phis.
360
361	Example scenario:
362
363	BB1:
364	flag_1 = phi <0, 1> // (1)
365	var_1 = phi <undef, some_val>
366
367
368	BB2:
369	flag_2 = phi <0, flag_1, flag_1> // (2)
370	var_2 = phi <undef, var_1, var_1>
371	if (flag_2 == 1)
372	goto BB3;
373
374	BB3:
375	use of var_2 // (3)
376
377	Because some flag arg in (1) is not constant, if we do not look into
378	the flag phis recursively, it is conservatively treated as unknown and
379	var_1 is thought to flow into use at (3). Since var_1 is potentially
380	uninitialized a false warning will be emitted.
381	Checking recursively into (1), the compiler can find out that only
382	some_val (which is defined) can flow into (3) which is OK. */
383
384	bool
385	uninit_analysis::prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def,
386	tree boundary_cst, tree_code cmp_code,
387	hash_set<gphi *> *visited_phis,
388	bitmap *visited_flag_phis)
389	{
390	/* The Boolean predicate guarding the PHI definition. Initialized
391	lazily from PHI in the first call to is_use_guarded() and cached
392	for subsequent iterations. */
393	uninit_analysis def_preds (m_eval);
394
395	unsigned n = MIN (m_eval.max_phi_args, gimple_phi_num_args (flag_def));
396	for (unsigned i = 0; i < n; i++)
397	{
398	if (!MASK_TEST_BIT (opnds, i))
399	continue;
400
401	tree flag_arg = gimple_phi_arg_def (gs: flag_def, index: i);
402	if (!is_gimple_constant (t: flag_arg))
403	{
404	if (TREE_CODE (flag_arg) != SSA_NAME)
405	return false;
406
407	gphi *flag_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (flag_arg));
408	if (!flag_arg_def)
409	return false;
410
411	tree phi_arg = gimple_phi_arg_def (gs: phi, index: i);
412	if (TREE_CODE (phi_arg) != SSA_NAME)
413	return false;
414
415	gphi *phi_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (phi_arg));
416	if (!phi_arg_def)
417	return false;
418
419	if (gimple_bb (g: phi_arg_def) != gimple_bb (g: flag_arg_def))
420	return false;
421
422	if (!*visited_flag_phis)
423	*visited_flag_phis = BITMAP_ALLOC (NULL);
424
425	tree phi_result = gimple_phi_result (gs: flag_arg_def);
426	if (bitmap_bit_p (*visited_flag_phis, SSA_NAME_VERSION (phi_result)))
427	return false;
428
429	bitmap_set_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
430
431	/* Now recursively try to prune the interesting phi args. */
432	unsigned opnds_arg_phi = m_eval.phi_arg_set (phi_arg_def);
433	if (!prune_phi_opnds (phi: phi_arg_def, opnds: opnds_arg_phi, flag_def: flag_arg_def,
434	boundary_cst, cmp_code, visited_phis,
435	visited_flag_phis))
436	return false;
437
438	bitmap_clear_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
439	continue;
440	}
441
442	/* Now check if the constant is in the guarded range. */
443	if (is_value_included_in (val: flag_arg, boundary: boundary_cst, cmpc: cmp_code))
444	{
445	/* Now that we know that this undefined edge is not pruned.
446	If the operand is defined by another phi, we can further
447	prune the incoming edges of that phi by checking
448	the predicates of this operands. */
449
450	tree opnd = gimple_phi_arg_def (gs: phi, index: i);
451	gimple *opnd_def = SSA_NAME_DEF_STMT (opnd);
452	if (gphi *opnd_def_phi = dyn_cast <gphi *> (p: opnd_def))
453	{
454	unsigned opnds2 = m_eval.phi_arg_set (opnd_def_phi);
455	if (!MASK_EMPTY (opnds2))
456	{
457	edge opnd_edge = gimple_phi_arg_edge (phi, i);
458	if (def_preds.is_use_guarded (phi, opnd_edge->src,
459	opnd_def_phi, opnds2,
460	visited_phis))
461	return false;
462	}
463	}
464	else
465	return false;
466	}
467	}
468
469	return true;
470	}
471
472	/* Recursively compute the set PHI's incoming edges with "uninteresting"
473	operands of a phi chain, i.e., those for which EVAL returns false.
474	CD_ROOT is the control dependence root from which edges are collected
475	up the CFG nodes that it's dominated by. *EDGES holds the result, and
476	VISITED is used for detecting cycles. */
477
478	void
479	uninit_analysis::collect_phi_def_edges (gphi *phi, basic_block cd_root,
480	vec<edge> *edges,
481	hash_set<gimple *> *visited)
482	{
483	if (visited->elements () == 0
484	&& DEBUG_PREDICATE_ANALYZER
485	&& dump_file)
486	{
487	fprintf (stream: dump_file, format: "%s for cd_root %u and ",
488	__func__, cd_root->index);
489	print_gimple_stmt (dump_file, phi, 0);
490
491	}
492
493	if (visited->add (k: phi))
494	return;
495
496	unsigned n = gimple_phi_num_args (gs: phi);
497	unsigned opnds_arg_phi = m_eval.phi_arg_set (phi);
498	for (unsigned i = 0; i < n; i++)
499	{
500	if (!MASK_TEST_BIT (opnds_arg_phi, i))
501	{
502	/* Add the edge for a not maybe-undefined edge value. */
503	edge opnd_edge = gimple_phi_arg_edge (phi, i);
504	if (dump_file && (dump_flags & TDF_DETAILS))
505	{
506	fprintf (stream: dump_file,
507	format: "\tFound def edge %i -> %i for cd_root %i "
508	"and operand %u of: ",
509	opnd_edge->src->index, opnd_edge->dest->index,
510	cd_root->index, i);
511	print_gimple_stmt (dump_file, phi, 0);
512	}
513	edges->safe_push (obj: opnd_edge);
514	continue;
515	}
516	else
517	{
518	tree opnd = gimple_phi_arg_def (gs: phi, index: i);
519	if (TREE_CODE (opnd) == SSA_NAME)
520	{
521	gimple *def = SSA_NAME_DEF_STMT (opnd);
522	if (gimple_code (g: def) == GIMPLE_PHI
523	&& dominated_by_p (CDI_DOMINATORS, gimple_bb (g: def), cd_root))
524	/* Process PHI defs of maybe-undefined edge values
525	recursively. */
526	collect_phi_def_edges (phi: as_a<gphi *> (p: def), cd_root, edges,
527	visited);
528	}
529	}
530	}
531	}
532
533	/* Return a bitset of all PHI arguments or zero if there are too many. */
534
535	unsigned
536	uninit_analysis::func_t::phi_arg_set (gphi *phi)
537	{
538	unsigned n = gimple_phi_num_args (gs: phi);
539
540	if (max_phi_args < n)
541	return 0;
542
543	/* Set the least significant N bits. */
544	return (1U << n) - 1;
545	}
546
547	/* Determine if the predicate set of the use does not overlap with that
548	of the interesting paths. The most common senario of guarded use is
549	in Example 1:
550	Example 1:
551	if (some_cond)
552	{
553	x = ...; // set x to valid
554	flag = true;
555	}
556
557	... some code ...
558
559	if (flag)
560	use (x); // use when x is valid
561
562	The real world examples are usually more complicated, but similar
563	and usually result from inlining:
564
565	bool init_func (int * x)
566	{
567	if (some_cond)
568	return false;
569	*x = ...; // set *x to valid
570	return true;
571	}
572
573	void foo (..)
574	{
575	int x;
576
577	if (!init_func (&x))
578	return;
579
580	.. some_code ...
581	use (x); // use when x is valid
582	}
583
584	Another possible use scenario is in the following trivial example:
585
586	Example 2:
587	if (n > 0)
588	x = 1;
589	...
590	if (n > 0)
591	{
592	if (m < 2)
593	... = x;
594	}
595
596	Predicate analysis needs to compute the composite predicate:
597
598	1) 'x' use predicate: (n > 0) .AND. (m < 2)
599	2) 'x' default value (non-def) predicate: .NOT. (n > 0)
600	(the predicate chain for phi operand defs can be computed
601	starting from a bb that is control equivalent to the phi's
602	bb and is dominating the operand def.)
603
604	and check overlapping:
605	(n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
606	<==> false
607
608	This implementation provides a framework that can handle different
609	scenarios. (Note that many simple cases are handled properly without
610	the predicate analysis if jump threading eliminates the merge point
611	thus makes path-sensitive analysis unnecessary.)
612
613	PHI is the phi node whose incoming (undefined) paths need to be
614	pruned, and OPNDS is the bitmap holding interesting operand
615	positions. VISITED is the pointer set of phi stmts being
616	checked. */
617
618	bool
619	uninit_analysis::overlap (gphi *phi, unsigned opnds, hash_set<gphi *> *visited,
620	const predicate &use_preds)
621	{
622	gimple *flag_def = NULL;
623	tree boundary_cst = NULL_TREE;
624
625	/* Find within the common prefix of multiple predicate chains
626	a predicate that is a comparison of a flag variable against
627	a constant. */
628	unsigned i = 0;
629	tree_code cmp_code;
630	while ((cmp_code = find_var_cmp_const (preds: use_preds.chain (), phi, flag_def: &flag_def,
631	boundary_cst: &boundary_cst, i)) != ERROR_MARK)
632	{
633	/* Now check all the uninit incoming edges have a constant flag
634	value that is in conflict with the use guard/predicate. */
635	bitmap visited_flag_phis = NULL;
636	gphi *phi_def = as_a<gphi *> (p: flag_def);
637	bool all_pruned = prune_phi_opnds (phi, opnds, flag_def: phi_def, boundary_cst,
638	cmp_code, visited_phis: visited,
639	visited_flag_phis: &visited_flag_phis);
640	if (visited_flag_phis)
641	BITMAP_FREE (visited_flag_phis);
642	if (all_pruned)
643	return false;
644	}
645
646	return true;
647	}
648
649	/* Return true if two predicates PRED1 and X2 are equivalent. Assume
650	the expressions have already properly re-associated. */
651
652	static inline bool
653	pred_equal_p (const pred_info &pred1, const pred_info &pred2)
654	{
655	if (!operand_equal_p (pred1.pred_lhs, pred2.pred_lhs, flags: 0)
656	|| !operand_equal_p (pred1.pred_rhs, pred2.pred_rhs, flags: 0))
657	return false;
658
659	tree_code c1 = pred1.cond_code, c2;
660	if (pred1.invert != pred2.invert
661	&& TREE_CODE_CLASS (pred2.cond_code) == tcc_comparison)
662	c2 = invert_tree_comparison (pred2.cond_code, false);
663	else
664	c2 = pred2.cond_code;
665
666	return c1 == c2;
667	}
668
669	/* Return true if PRED tests inequality (i.e., X != Y). */
670
671	static inline bool
672	is_neq_relop_p (const pred_info &pred)
673	{
674
675	return ((pred.cond_code == NE_EXPR && !pred.invert)
676	|| (pred.cond_code == EQ_EXPR && pred.invert));
677	}
678
679	/* Returns true if PRED is of the form X != 0. */
680
681	static inline bool
682	is_neq_zero_form_p (const pred_info &pred)
683	{
684	if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs)
685	|| TREE_CODE (pred.pred_lhs) != SSA_NAME)
686	return false;
687	return true;
688	}
689
690	/* Return true if PRED is equivalent to X != 0. */
691
692	static inline bool
693	pred_expr_equal_p (const pred_info &pred, tree expr)
694	{
695	if (!is_neq_zero_form_p (pred))
696	return false;
697
698	return operand_equal_p (pred.pred_lhs, expr, flags: 0);
699	}
700
701	/* Return true if VAL satisfies (x CMPC BOUNDARY) predicate. CMPC can
702	be either one of the range comparison codes ({GE,LT,EQ,NE}_EXPR and
703	the like), or BIT_AND_EXPR. EXACT_P is only meaningful for the latter.
704	Modify the question from VAL & BOUNDARY != 0 to VAL & BOUNDARY == VAL.
705	For other values of CMPC, EXACT_P is ignored. */
706
707	static bool
708	value_sat_pred_p (tree val, tree boundary, tree_code cmpc,
709	bool exact_p = false)
710	{
711	if (cmpc != BIT_AND_EXPR)
712	return is_value_included_in (val, boundary, cmpc);
713
714	widest_int andw = wi::to_widest (t: val) & wi::to_widest (t: boundary);
715	if (exact_p)
716	return andw == wi::to_widest (t: val);
717
718	return wi::ne_p (x: andw, y: 0);
719	}
720
721	/* Return true if the domain of single predicate expression PRED1
722	is a subset of that of PRED2, and false if it cannot be proved. */
723
724	static bool
725	subset_of (const pred_info &pred1, const pred_info &pred2)
726	{
727	if (pred_equal_p (pred1, pred2))
728	return true;
729
730	if ((TREE_CODE (pred1.pred_rhs) != INTEGER_CST)
731	|| (TREE_CODE (pred2.pred_rhs) != INTEGER_CST))
732	return false;
733
734	if (!operand_equal_p (pred1.pred_lhs, pred2.pred_lhs, flags: 0))
735	return false;
736
737	tree_code code1 = pred1.cond_code;
738	if (pred1.invert)
739	code1 = invert_tree_comparison (code1, false);
740	tree_code code2 = pred2.cond_code;
741	if (pred2.invert)
742	code2 = invert_tree_comparison (code2, false);
743
744	if (code2 == NE_EXPR && code1 == NE_EXPR)
745	return false;
746
747	if (code2 == NE_EXPR)
748	return !value_sat_pred_p (val: pred2.pred_rhs, boundary: pred1.pred_rhs, cmpc: code1);
749
750	if (code1 == EQ_EXPR)
751	return value_sat_pred_p (val: pred1.pred_rhs, boundary: pred2.pred_rhs, cmpc: code2);
752
753	if (code1 == code2)
754	return value_sat_pred_p (val: pred1.pred_rhs, boundary: pred2.pred_rhs, cmpc: code2,
755	exact_p: code1 == BIT_AND_EXPR);
756
757	return false;
758	}
759
760	/* Return true if the domain of CHAIN1 is a subset of that of CHAIN2.
761	Return false if it cannot be proven so. */
762
763	static bool
764	subset_of (const pred_chain &chain1, const pred_chain &chain2)
765	{
766	unsigned np1 = chain1.length ();
767	unsigned np2 = chain2.length ();
768	for (unsigned i2 = 0; i2 < np2; i2++)
769	{
770	bool found = false;
771	const pred_info &info2 = chain2[i2];
772	for (unsigned i1 = 0; i1 < np1; i1++)
773	{
774	const pred_info &info1 = chain1[i1];
775	if (subset_of (pred1: info1, pred2: info2))
776	{
777	found = true;
778	break;
779	}
780	}
781	if (!found)
782	return false;
783	}
784	return true;
785	}
786
787	/* Return true if the domain defined by the predicate chain PREDS is
788	a subset of the domain of *THIS. Return false if PREDS's domain
789	is not a subset of any of the sub-domains of *THIS (corresponding
790	to each individual chains in it), even though it may be still be
791	a subset of whole domain of *THIS which is the union (ORed) of all
792	its subdomains. In other words, the result is conservative. */
793
794	bool
795	predicate::includes (const pred_chain &chain) const
796	{
797	for (unsigned i = 0; i < m_preds.length (); i++)
798	if (subset_of (chain1: chain, chain2: m_preds[i]))
799	return true;
800
801	return false;
802	}
803
804	/* Return true if the domain defined by *THIS is a superset of PREDS's
805	domain.
806	Avoid building generic trees (and rely on the folding capability
807	of the compiler), and instead perform brute force comparison of
808	individual predicate chains (this won't be a computationally costly
809	since the chains are pretty short). Returning false does not
810	necessarily mean *THIS is not a superset of *PREDS, only that
811	it need not be since the analysis cannot prove it. */
812
813	bool
814	predicate::superset_of (const predicate &preds) const
815	{
816	for (unsigned i = 0; i < preds.m_preds.length (); i++)
817	if (!includes (chain: preds.m_preds[i]))
818	return false;
819
820	return true;
821	}
822
823	/* Create a predicate of the form OP != 0 and push it the work list CHAIN. */
824
825	static void
826	push_to_worklist (tree op, pred_chain *chain, hash_set<tree> *mark_set)
827	{
828	if (mark_set->contains (k: op))
829	return;
830	mark_set->add (k: op);
831
832	pred_info arg_pred;
833	arg_pred.pred_lhs = op;
834	arg_pred.pred_rhs = integer_zero_node;
835	arg_pred.cond_code = NE_EXPR;
836	arg_pred.invert = false;
837	chain->safe_push (obj: arg_pred);
838	}
839
840	/* Return a pred_info for a gimple assignment CMP_ASSIGN with comparison
841	rhs. */
842
843	static pred_info
844	get_pred_info_from_cmp (const gimple *cmp_assign)
845	{
846	pred_info pred;
847	pred.pred_lhs = gimple_assign_rhs1 (gs: cmp_assign);
848	pred.pred_rhs = gimple_assign_rhs2 (gs: cmp_assign);
849	pred.cond_code = gimple_assign_rhs_code (gs: cmp_assign);
850	pred.invert = false;
851	return pred;
852	}
853
854	/* If PHI is a degenerate phi with all operands having the same value (relop)
855	update *PRED to that value and return true. Otherwise return false. */
856
857	static bool
858	is_degenerate_phi (gimple *phi, pred_info *pred)
859	{
860	tree op0 = gimple_phi_arg_def (gs: phi, index: 0);
861
862	if (TREE_CODE (op0) != SSA_NAME)
863	return false;
864
865	gimple *def0 = SSA_NAME_DEF_STMT (op0);
866	if (gimple_code (g: def0) != GIMPLE_ASSIGN)
867	return false;
868
869	if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0)) != tcc_comparison)
870	return false;
871
872	pred_info pred0 = get_pred_info_from_cmp (cmp_assign: def0);
873
874	unsigned n = gimple_phi_num_args (gs: phi);
875	for (unsigned i = 1; i < n; ++i)
876	{
877	tree op = gimple_phi_arg_def (gs: phi, index: i);
878	if (TREE_CODE (op) != SSA_NAME)
879	return false;
880
881	gimple *def = SSA_NAME_DEF_STMT (op);
882	if (gimple_code (g: def) != GIMPLE_ASSIGN)
883	return false;
884
885	if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
886	return false;
887
888	pred_info pred = get_pred_info_from_cmp (cmp_assign: def);
889	if (!pred_equal_p (pred1: pred, pred2: pred0))
890	return false;
891	}
892
893	*pred = pred0;
894	return true;
895	}
896
897	/* If compute_control_dep_chain bailed out due to limits this routine
898	tries to build a partial sparse path using dominators. Returns
899	path edges whose predicates are always true when reaching E. */
900
901	static void
902	simple_control_dep_chain (vec<edge>& chain, basic_block from, basic_block to)
903	{
904	if (!dominated_by_p (CDI_DOMINATORS, to, from))
905	return;
906
907	basic_block src = to;
908	while (src != from
909	&& chain.length () <= MAX_CHAIN_LEN)
910	{
911	basic_block dest = src;
912	src = get_immediate_dominator (CDI_DOMINATORS, src);
913	if (single_pred_p (bb: dest))
914	{
915	edge pred_e = single_pred_edge (bb: dest);
916	gcc_assert (pred_e->src == src);
917	if (!(pred_e->flags & ((EDGE_FAKE | EDGE_ABNORMAL | EDGE_DFS_BACK)))
918	&& !single_succ_p (bb: src))
919	chain.safe_push (obj: pred_e);
920	}
921	}
922	}
923
924	/* Perform a DFS walk on predecessor edges to mark the region denoted
925	by the EXIT_SRC block and DOM which dominates EXIT_SRC, including DOM.
926	Blocks in the region are marked with FLAG and added to BBS. BBS is
927	filled up to its capacity only after which the walk is terminated
928	and false is returned. If the whole region was marked, true is returned. */
929
930	static bool
931	dfs_mark_dominating_region (basic_block exit_src, basic_block dom, int flag,
932	vec<basic_block> &bbs)
933	{
934	if (exit_src == dom || exit_src->flags & flag)
935	return true;
936	if (!bbs.space (nelems: 1))
937	return false;
938	bbs.quick_push (obj: exit_src);
939	exit_src->flags |= flag;
940	auto_vec<edge_iterator, 20> stack (bbs.allocated () - bbs.length () + 1);
941	stack.quick_push (ei_start (exit_src->preds));
942	while (!stack.is_empty ())
943	{
944	/* Look at the edge on the top of the stack. */
945	edge_iterator ei = stack.last ();
946	basic_block src = ei_edge (i: ei)->src;
947
948	/* Check if the edge source has been visited yet. */
949	if (!(src->flags & flag))
950	{
951	/* Mark the source if there's still space. If not, return early. */
952	if (!bbs.space (nelems: 1))
953	return false;
954	src->flags |= flag;
955	bbs.quick_push (obj: src);
956
957	/* Queue its predecessors if we didn't reach DOM. */
958	if (src != dom && EDGE_COUNT (src->preds) > 0)
959	stack.quick_push (ei_start (src->preds));
960	}
961	else
962	{
963	if (!ei_one_before_end_p (i: ei))
964	ei_next (i: &stack.last ());
965	else
966	stack.pop ();
967	}
968	}
969	return true;
970	}
971
972	static bool
973	compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
974	vec<edge> cd_chains[], unsigned *num_chains,
975	vec<edge> &cur_cd_chain, unsigned *num_calls,
976	unsigned in_region, unsigned depth,
977	bool *complete_p);
978
979	/* Helper for compute_control_dep_chain that walks the post-dominator
980	chain from CD_BB up unto TARGET_BB looking for paths to DEP_BB. */
981
982	static bool
983	compute_control_dep_chain_pdom (basic_block cd_bb, const_basic_block dep_bb,
984	basic_block target_bb,
985	vec<edge> cd_chains[], unsigned *num_chains,
986	vec<edge> &cur_cd_chain, unsigned *num_calls,
987	unsigned in_region, unsigned depth,
988	bool *complete_p)
989	{
990	bool found_cd_chain = false;
991	while (cd_bb != target_bb)
992	{
993	if (cd_bb == dep_bb)
994	{
995	/* Found a direct control dependence. */
996	if (*num_chains < MAX_NUM_CHAINS)
997	{
998	if (DEBUG_PREDICATE_ANALYZER && dump_file)
999	fprintf (stream: dump_file, format: "%*s pushing { %s }\n",
1000	depth, "", format_edge_vec (ev: cur_cd_chain).c_str ());
1001	cd_chains[*num_chains] = cur_cd_chain.copy ();
1002	(*num_chains)++;
1003	}
1004	found_cd_chain = true;
1005	/* Check path from next edge. */
1006	break;
1007	}
1008
1009	/* If the dominating region has been marked avoid walking outside. */
1010	if (in_region != 0 && !(cd_bb->flags & in_region))
1011	break;
1012
1013	/* Count the number of steps we perform to limit compile-time.
1014	This should cover both recursion and the post-dominator walk. */
1015	if (*num_calls > (unsigned)param_uninit_control_dep_attempts)
1016	{
1017	if (dump_file)
1018	fprintf (stream: dump_file, format: "param_uninit_control_dep_attempts "
1019	"exceeded: %u\n", *num_calls);
1020	*complete_p = false;
1021	break;
1022	}
1023	++*num_calls;
1024
1025	/* Check if DEP_BB is indirectly control-dependent on DOM_BB. */
1026	if (!single_succ_p (bb: cd_bb)
1027	&& compute_control_dep_chain (dom_bb: cd_bb, dep_bb, cd_chains,
1028	num_chains, cur_cd_chain,
1029	num_calls, in_region, depth: depth + 1,
1030	complete_p))
1031	{
1032	found_cd_chain = true;
1033	break;
1034	}
1035
1036	/* The post-dominator walk will reach a backedge only
1037	from a forwarder, otherwise it should choose to exit
1038	the SCC. */
1039	if (single_succ_p (bb: cd_bb)
1040	&& single_succ_edge (bb: cd_bb)->flags & EDGE_DFS_BACK)
1041	break;
1042	basic_block prev_cd_bb = cd_bb;
1043	cd_bb = get_immediate_dominator (CDI_POST_DOMINATORS, cd_bb);
1044	if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1045	break;
1046	/* Pick up conditions toward the post dominator such like
1047	loop exit conditions. See gcc.dg/uninit-pred-11.c and
1048	gcc.dg/unninit-pred-12.c and PR106754. */
1049	if (single_pred_p (bb: cd_bb))
1050	{
1051	edge e2 = single_pred_edge (bb: cd_bb);
1052	gcc_assert (e2->src == prev_cd_bb);
1053	/* But avoid adding fallthru or abnormal edges. */
1054	if (!(e2->flags & (EDGE_FAKE | EDGE_ABNORMAL | EDGE_DFS_BACK))
1055	&& !single_succ_p (bb: prev_cd_bb))
1056	cur_cd_chain.safe_push (obj: e2);
1057	}
1058	}
1059	return found_cd_chain;
1060	}
1061
1062
1063	/* Recursively compute the control dependence chains (paths of edges)
1064	from the dependent basic block, DEP_BB, up to the dominating basic
1065	block, DOM_BB (the head node of a chain should be dominated by it),
1066	storing them in the CD_CHAINS array.
1067	CUR_CD_CHAIN is the current chain being computed.
1068	*NUM_CHAINS is total number of chains in the CD_CHAINS array.
1069	*NUM_CALLS is the number of recursive calls to control unbounded
1070	recursion.
1071	Return true if the information is successfully computed, false if
1072	there is no control dependence or not computed.
1073	*COMPLETE_P is set to false if we stopped walking due to limits.
1074	In this case there might be missing chains. */
1075
1076	static bool
1077	compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
1078	vec<edge> cd_chains[], unsigned *num_chains,
1079	vec<edge> &cur_cd_chain, unsigned *num_calls,
1080	unsigned in_region, unsigned depth,
1081	bool *complete_p)
1082	{
1083	/* In our recursive calls this doesn't happen. */
1084	if (single_succ_p (bb: dom_bb))
1085	return false;
1086
1087	/* FIXME: Use a set instead. */
1088	unsigned cur_chain_len = cur_cd_chain.length ();
1089	if (cur_chain_len > MAX_CHAIN_LEN)
1090	{
1091	if (dump_file)
1092	fprintf (stream: dump_file, format: "MAX_CHAIN_LEN exceeded: %u\n", cur_chain_len);
1093
1094	*complete_p = false;
1095	return false;
1096	}
1097
1098	if (cur_chain_len > 5)
1099	{
1100	if (dump_file)
1101	fprintf (stream: dump_file, format: "chain length exceeds 5: %u\n", cur_chain_len);
1102	}
1103
1104	if (DEBUG_PREDICATE_ANALYZER && dump_file)
1105	fprintf (stream: dump_file,
1106	format: "%*s%s (dom_bb = %u, dep_bb = %u, ..., "
1107	"cur_cd_chain = { %s }, ...)\n",
1108	depth, "", __func__, dom_bb->index, dep_bb->index,
1109	format_edge_vec (ev: cur_cd_chain).c_str ());
1110
1111	bool found_cd_chain = false;
1112
1113	/* Iterate over DOM_BB's successors. */
1114	edge e;
1115	edge_iterator ei;
1116	FOR_EACH_EDGE (e, ei, dom_bb->succs)
1117	{
1118	if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL | EDGE_DFS_BACK))
1119	continue;
1120
1121	basic_block cd_bb = e->dest;
1122	unsigned pop_mark = cur_cd_chain.length ();
1123	cur_cd_chain.safe_push (obj: e);
1124	basic_block target_bb
1125	= get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb);
1126	/* Walk the post-dominator chain up to the CFG merge. */
1127	found_cd_chain
1128	|= compute_control_dep_chain_pdom (cd_bb, dep_bb, target_bb,
1129	cd_chains, num_chains,
1130	cur_cd_chain, num_calls,
1131	in_region, depth, complete_p);
1132	cur_cd_chain.truncate (size: pop_mark);
1133	gcc_assert (cur_cd_chain.length () == cur_chain_len);
1134	}
1135
1136	gcc_assert (cur_cd_chain.length () == cur_chain_len);
1137	return found_cd_chain;
1138	}
1139
1140	/* Wrapper around the compute_control_dep_chain worker above. Returns
1141	true when the collected set of chains in CD_CHAINS is complete. */
1142
1143	static bool
1144	compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
1145	vec<edge> cd_chains[], unsigned *num_chains,
1146	unsigned in_region = 0)
1147	{
1148	auto_vec<edge, 10> cur_cd_chain;
1149	unsigned num_calls = 0;
1150	unsigned depth = 0;
1151	bool complete_p = true;
1152	/* Walk the post-dominator chain. */
1153	cur_cd_chain.reserve (MAX_CHAIN_LEN + 1);
1154	compute_control_dep_chain_pdom (cd_bb: dom_bb, dep_bb, NULL, cd_chains,
1155	num_chains, cur_cd_chain, num_calls: &num_calls,
1156	in_region, depth, complete_p: &complete_p);
1157	return complete_p;
1158	}
1159
1160	/* Implemented simplifications:
1161
1162	1a) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1163	1b) [!](X rel y) AND [!](X rel y') where y == y' or both constant
1164	can possibly be simplified
1165	2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1166	3) X OR (!X AND Y) is equivalent to (X OR Y);
1167	4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1168	(x != 0 AND y != 0)
1169	5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1170	(X AND Y) OR Z
1171
1172	PREDS is the predicate chains, and N is the number of chains. */
1173
1174	/* Implement rule 1a above. PREDS is the AND predicate to simplify
1175	in place. */
1176
1177	static void
1178	simplify_1a (pred_chain &chain)
1179	{
1180	bool simplified = false;
1181	pred_chain s_chain = vNULL;
1182
1183	unsigned n = chain.length ();
1184	for (unsigned i = 0; i < n; i++)
1185	{
1186	pred_info &a_pred = chain[i];
1187
1188	if (!a_pred.pred_lhs
1189	|| !is_neq_zero_form_p (pred: a_pred))
1190	continue;
1191
1192	gimple *def_stmt = SSA_NAME_DEF_STMT (a_pred.pred_lhs);
1193	if (gimple_code (g: def_stmt) != GIMPLE_ASSIGN)
1194	continue;
1195
1196	if (gimple_assign_rhs_code (gs: def_stmt) != BIT_IOR_EXPR)
1197	continue;
1198
1199	for (unsigned j = 0; j < n; j++)
1200	{
1201	const pred_info &b_pred = chain[j];
1202
1203	if (!b_pred.pred_lhs
1204	|| !is_neq_zero_form_p (pred: b_pred))
1205	continue;
1206
1207	if (pred_expr_equal_p (pred: b_pred, expr: gimple_assign_rhs1 (gs: def_stmt))
1208	|| pred_expr_equal_p (pred: b_pred, expr: gimple_assign_rhs2 (gs: def_stmt)))
1209	{
1210	/* Mark A_PRED for removal from PREDS. */
1211	a_pred.pred_lhs = NULL;
1212	a_pred.pred_rhs = NULL;
1213	simplified = true;
1214	break;
1215	}
1216	}
1217	}
1218
1219	if (!simplified)
1220	return;
1221
1222	/* Remove predicates marked above. */
1223	for (unsigned i = 0; i < n; i++)
1224	{
1225	pred_info &a_pred = chain[i];
1226	if (!a_pred.pred_lhs)
1227	continue;
1228	s_chain.safe_push (obj: a_pred);
1229	}
1230
1231	chain.release ();
1232	chain = s_chain;
1233	}
1234
1235	/* Implement rule 1b above. PREDS is the AND predicate to simplify
1236	in place. Returns true if CHAIN simplifies to true or false. */
1237
1238	static bool
1239	simplify_1b (pred_chain &chain)
1240	{
1241	for (unsigned i = 0; i < chain.length (); i++)
1242	{
1243	pred_info &a_pred = chain[i];
1244
1245	for (unsigned j = i + 1; j < chain.length (); ++j)
1246	{
1247	pred_info &b_pred = chain[j];
1248
1249	if (!operand_equal_p (a_pred.pred_lhs, b_pred.pred_lhs)
1250	|| (!operand_equal_p (a_pred.pred_rhs, b_pred.pred_rhs)
1251	&& !(CONSTANT_CLASS_P (a_pred.pred_rhs)
1252	&& CONSTANT_CLASS_P (b_pred.pred_rhs))))
1253	continue;
1254
1255	tree_code a_code = a_pred.cond_code;
1256	if (a_pred.invert)
1257	a_code = invert_tree_comparison (a_code, false);
1258	tree_code b_code = b_pred.cond_code;
1259	if (b_pred.invert)
1260	b_code = invert_tree_comparison (b_code, false);
1261	/* Try to combine X a_code Y && X b_code Y'. */
1262	tree comb = maybe_fold_and_comparisons (boolean_type_node,
1263	a_code,
1264	a_pred.pred_lhs,
1265	a_pred.pred_rhs,
1266	b_code,
1267	b_pred.pred_lhs,
1268	b_pred.pred_rhs, NULL);
1269	if (!comb)
1270	;
1271	else if (integer_zerop (comb))
1272	return true;
1273	else if (integer_truep (comb))
1274	{
1275	chain.ordered_remove (ix: j);
1276	chain.ordered_remove (ix: i);
1277	if (chain.is_empty ())
1278	return true;
1279	i--;
1280	break;
1281	}
1282	else if (COMPARISON_CLASS_P (comb)
1283	&& operand_equal_p (a_pred.pred_lhs, TREE_OPERAND (comb, 0)))
1284	{
1285	chain.ordered_remove (ix: j);
1286	a_pred.cond_code = TREE_CODE (comb);
1287	a_pred.pred_rhs = TREE_OPERAND (comb, 1);
1288	a_pred.invert = false;
1289	j--;
1290	}
1291	}
1292	}
1293
1294	return false;
1295	}
1296
1297	/* Implements rule 2 for the OR predicate PREDS:
1298
1299	2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1300
1301	bool
1302	predicate::simplify_2 ()
1303	{
1304	bool simplified = false;
1305
1306	/* (X AND Y) OR (!X AND Y) is equivalent to Y.
1307	(X AND Y) OR (X AND !Y) is equivalent to X. */
1308
1309	for (unsigned i = 0; i < m_preds.length (); i++)
1310	{
1311	pred_chain &a_chain = m_preds[i];
1312
1313	for (unsigned j = i + 1; j < m_preds.length (); j++)
1314	{
1315	pred_chain &b_chain = m_preds[j];
1316	if (b_chain.length () != a_chain.length ())
1317	continue;
1318
1319	unsigned neg_idx = -1U;
1320	for (unsigned k = 0; k < a_chain.length (); ++k)
1321	{
1322	if (pred_equal_p (pred1: a_chain[k], pred2: b_chain[k]))
1323	continue;
1324	if (neg_idx != -1U)
1325	{
1326	neg_idx = -1U;
1327	break;
1328	}
1329	if (pred_neg_p (x1: a_chain[k], x2: b_chain[k]))
1330	neg_idx = k;
1331	else
1332	break;
1333	}
1334	/* If we found equal chains with one negated predicate
1335	simplify. */
1336	if (neg_idx != -1U)
1337	{
1338	a_chain.ordered_remove (ix: neg_idx);
1339	m_preds.ordered_remove (ix: j);
1340	simplified = true;
1341	if (a_chain.is_empty ())
1342	{
1343	/* A && !A simplifies to true, wipe the whole predicate. */
1344	for (unsigned k = 0; k < m_preds.length (); ++k)
1345	m_preds[k].release ();
1346	m_preds.truncate (size: 0);
1347	}
1348	break;
1349	}
1350	}
1351	}
1352
1353	return simplified;
1354	}
1355
1356	/* Implement rule 3 for the OR predicate PREDS:
1357
1358	3) x OR (!x AND y) is equivalent to x OR y. */
1359
1360	bool
1361	predicate::simplify_3 ()
1362	{
1363	/* Now iteratively simplify X OR (!X AND Z ..)
1364	into X OR (Z ...). */
1365
1366	unsigned n = m_preds.length ();
1367	if (n < 2)
1368	return false;
1369
1370	bool simplified = false;
1371	for (unsigned i = 0; i < n; i++)
1372	{
1373	const pred_chain &a_chain = m_preds[i];
1374
1375	if (a_chain.length () != 1)
1376	continue;
1377
1378	const pred_info &x = a_chain[0];
1379	for (unsigned j = 0; j < n; j++)
1380	{
1381	if (j == i)
1382	continue;
1383
1384	pred_chain b_chain = m_preds[j];
1385	if (b_chain.length () < 2)
1386	continue;
1387
1388	for (unsigned k = 0; k < b_chain.length (); k++)
1389	{
1390	const pred_info &x2 = b_chain[k];
1391	if (pred_neg_p (x1: x, x2))
1392	{
1393	b_chain.unordered_remove (ix: k);
1394	simplified = true;
1395	break;
1396	}
1397	}
1398	}
1399	}
1400	return simplified;
1401	}
1402
1403	/* Implement rule 4 for the OR predicate PREDS:
1404
1405	2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1406	(x != 0 AND y != 0). */
1407
1408	bool
1409	predicate::simplify_4 ()
1410	{
1411	bool simplified = false;
1412	pred_chain_union s_preds = vNULL;
1413
1414	unsigned n = m_preds.length ();
1415	for (unsigned i = 0; i < n; i++)
1416	{
1417	pred_chain a_chain = m_preds[i];
1418	if (a_chain.length () != 1)
1419	continue;
1420
1421	const pred_info &z = a_chain[0];
1422	if (!is_neq_zero_form_p (pred: z))
1423	continue;
1424
1425	gimple *def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
1426	if (gimple_code (g: def_stmt) != GIMPLE_ASSIGN)
1427	continue;
1428
1429	if (gimple_assign_rhs_code (gs: def_stmt) != BIT_AND_EXPR)
1430	continue;
1431
1432	for (unsigned j = 0; j < n; j++)
1433	{
1434	if (j == i)
1435	continue;
1436
1437	pred_chain b_chain = m_preds[j];
1438	if (b_chain.length () != 2)
1439	continue;
1440
1441	const pred_info &x2 = b_chain[0];
1442	const pred_info &y2 = b_chain[1];
1443	if (!is_neq_zero_form_p (pred: x2) || !is_neq_zero_form_p (pred: y2))
1444	continue;
1445
1446	if ((pred_expr_equal_p (pred: x2, expr: gimple_assign_rhs1 (gs: def_stmt))
1447	&& pred_expr_equal_p (pred: y2, expr: gimple_assign_rhs2 (gs: def_stmt)))
1448	|| (pred_expr_equal_p (pred: x2, expr: gimple_assign_rhs2 (gs: def_stmt))
1449	&& pred_expr_equal_p (pred: y2, expr: gimple_assign_rhs1 (gs: def_stmt))))
1450	{
1451	/* Kill a_chain. */
1452	a_chain.release ();
1453	simplified = true;
1454	break;
1455	}
1456	}
1457	}
1458	/* Now clean up the chain. */
1459	if (simplified)
1460	{
1461	for (unsigned i = 0; i < n; i++)
1462	{
1463	if (m_preds[i].is_empty ())
1464	continue;
1465	s_preds.safe_push (obj: m_preds[i]);
1466	}
1467
1468	m_preds.release ();
1469	m_preds = s_preds;
1470	s_preds = vNULL;
1471	}
1472
1473	return simplified;
1474	}
1475
1476	/* Simplify predicates in *THIS. */
1477
1478	void
1479	predicate::simplify (gimple *use_or_def, bool is_use)
1480	{
1481	if (dump_file && dump_flags & TDF_DETAILS)
1482	{
1483	fprintf (stream: dump_file, format: "Before simplication ");
1484	dump (dump_file, use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
1485	}
1486
1487	for (unsigned i = 0; i < m_preds.length (); i++)
1488	{
1489	::simplify_1a (chain&: m_preds[i]);
1490	if (::simplify_1b (chain&: m_preds[i]))
1491	{
1492	m_preds[i].release ();
1493	m_preds.ordered_remove (ix: i);
1494	i--;
1495	}
1496	}
1497
1498	if (m_preds.length () < 2)
1499	return;
1500
1501	bool changed;
1502	do
1503	{
1504	changed = false;
1505	if (simplify_2 ())
1506	changed = true;
1507
1508	if (simplify_3 ())
1509	changed = true;
1510
1511	if (simplify_4 ())
1512	changed = true;
1513	}
1514	while (changed);
1515	}
1516
1517	/* Attempt to normalize predicate chains by following UD chains by
1518	building up a big tree of either IOR operations or AND operations,
1519	and converting the IOR tree into a pred_chain_union or the BIT_AND
1520	tree into a pred_chain.
1521	Example:
1522
1523	_3 = _2 RELOP1 _1;
1524	_6 = _5 RELOP2 _4;
1525	_9 = _8 RELOP3 _7;
1526	_10 = _3 | _6;
1527	_12 = _9 | _0;
1528	_t = _10 | _12;
1529
1530	then _t != 0 will be normalized into a pred_chain_union
1531
1532	(_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1533
1534	Similarly given:
1535
1536	_3 = _2 RELOP1 _1;
1537	_6 = _5 RELOP2 _4;
1538	_9 = _8 RELOP3 _7;
1539	_10 = _3 & _6;
1540	_12 = _9 & _0;
1541
1542	then _t != 0 will be normalized into a pred_chain:
1543	(_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1544	*/
1545
1546	/* Normalize predicate PRED:
1547	1) if PRED can no longer be normalized, append it to *THIS.
1548	2) otherwise if PRED is of the form x != 0, follow x's definition
1549	and put normalized predicates into WORK_LIST. */
1550
1551	void
1552	predicate::normalize (pred_chain *norm_chain,
1553	pred_info pred,
1554	tree_code and_or_code,
1555	pred_chain *work_list,
1556	hash_set<tree> *mark_set)
1557	{
1558	if (!is_neq_zero_form_p (pred))
1559	{
1560	if (and_or_code == BIT_IOR_EXPR)
1561	push_pred (pred);
1562	else
1563	norm_chain->safe_push (obj: pred);
1564	return;
1565	}
1566
1567	gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
1568
1569	if (gimple_code (g: def_stmt) == GIMPLE_PHI
1570	&& is_degenerate_phi (phi: def_stmt, pred: &pred))
1571	/* PRED has been modified above. */
1572	work_list->safe_push (obj: pred);
1573	else if (gimple_code (g: def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR)
1574	{
1575	unsigned n = gimple_phi_num_args (gs: def_stmt);
1576
1577	/* Punt for a nonzero constant. The predicate should be one guarding
1578	the phi edge. */
1579	for (unsigned i = 0; i < n; ++i)
1580	{
1581	tree op = gimple_phi_arg_def (gs: def_stmt, index: i);
1582	if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
1583	{
1584	push_pred (pred);
1585	return;
1586	}
1587	}
1588
1589	for (unsigned i = 0; i < n; ++i)
1590	{
1591	tree op = gimple_phi_arg_def (gs: def_stmt, index: i);
1592	if (integer_zerop (op))
1593	continue;
1594
1595	push_to_worklist (op, chain: work_list, mark_set);
1596	}
1597	}
1598	else if (gimple_code (g: def_stmt) != GIMPLE_ASSIGN)
1599	{
1600	if (and_or_code == BIT_IOR_EXPR)
1601	push_pred (pred);
1602	else
1603	norm_chain->safe_push (obj: pred);
1604	}
1605	else if (gimple_assign_rhs_code (gs: def_stmt) == and_or_code)
1606	{
1607	/* Avoid splitting up bit manipulations like x & 3 or y | 1. */
1608	if (is_gimple_min_invariant (gimple_assign_rhs2 (gs: def_stmt)))
1609	{
1610	/* But treat x & 3 as a condition. */
1611	if (and_or_code == BIT_AND_EXPR)
1612	{
1613	pred_info n_pred;
1614	n_pred.pred_lhs = gimple_assign_rhs1 (gs: def_stmt);
1615	n_pred.pred_rhs = gimple_assign_rhs2 (gs: def_stmt);
1616	n_pred.cond_code = and_or_code;
1617	n_pred.invert = false;
1618	norm_chain->safe_push (obj: n_pred);
1619	}
1620	}
1621	else
1622	{
1623	push_to_worklist (op: gimple_assign_rhs1 (gs: def_stmt), chain: work_list, mark_set);
1624	push_to_worklist (op: gimple_assign_rhs2 (gs: def_stmt), chain: work_list, mark_set);
1625	}
1626	}
1627	else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
1628	== tcc_comparison)
1629	{
1630	pred_info n_pred = get_pred_info_from_cmp (cmp_assign: def_stmt);
1631	if (and_or_code == BIT_IOR_EXPR)
1632	push_pred (n_pred);
1633	else
1634	norm_chain->safe_push (obj: n_pred);
1635	}
1636	else
1637	{
1638	if (and_or_code == BIT_IOR_EXPR)
1639	push_pred (pred);
1640	else
1641	norm_chain->safe_push (obj: pred);
1642	}
1643	}
1644
1645	/* Normalize PRED and store the normalized predicates in THIS->M_PREDS. */
1646
1647	void
1648	predicate::normalize (const pred_info &pred)
1649	{
1650	if (!is_neq_zero_form_p (pred))
1651	{
1652	push_pred (pred);
1653	return;
1654	}
1655
1656	tree_code and_or_code = ERROR_MARK;
1657
1658	gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
1659	if (gimple_code (g: def_stmt) == GIMPLE_ASSIGN)
1660	and_or_code = gimple_assign_rhs_code (gs: def_stmt);
1661	if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR)
1662	{
1663	if (TREE_CODE_CLASS (and_or_code) == tcc_comparison)
1664	{
1665	pred_info n_pred = get_pred_info_from_cmp (cmp_assign: def_stmt);
1666	push_pred (n_pred);
1667	}
1668	else
1669	push_pred (pred);
1670	return;
1671	}
1672
1673
1674	pred_chain norm_chain = vNULL;
1675	pred_chain work_list = vNULL;
1676	work_list.safe_push (obj: pred);
1677	hash_set<tree> mark_set;
1678
1679	while (!work_list.is_empty ())
1680	{
1681	pred_info a_pred = work_list.pop ();
1682	normalize (norm_chain: &norm_chain, pred: a_pred, and_or_code, work_list: &work_list, mark_set: &mark_set);
1683	}
1684
1685	if (and_or_code == BIT_AND_EXPR)
1686	m_preds.safe_push (obj: norm_chain);
1687
1688	work_list.release ();
1689	}
1690
1691	/* Normalize a single predicate PRED_CHAIN and append it to *THIS. */
1692
1693	void
1694	predicate::normalize (const pred_chain &chain)
1695	{
1696	pred_chain work_list = vNULL;
1697	hash_set<tree> mark_set;
1698	for (unsigned i = 0; i < chain.length (); i++)
1699	{
1700	work_list.safe_push (obj: chain[i]);
1701	mark_set.add (k: chain[i].pred_lhs);
1702	}
1703
1704	/* Normalized chain of predicates built up below. */
1705	pred_chain norm_chain = vNULL;
1706	while (!work_list.is_empty ())
1707	{
1708	pred_info pi = work_list.pop ();
1709	/* The predicate object is not modified here, only NORM_CHAIN and
1710	WORK_LIST are appended to. */
1711	unsigned oldlen = m_preds.length ();
1712	normalize (norm_chain: &norm_chain, pred: pi, and_or_code: BIT_AND_EXPR, work_list: &work_list, mark_set: &mark_set);
1713	gcc_assert (m_preds.length () == oldlen);
1714	}
1715
1716	m_preds.safe_push (obj: norm_chain);
1717	work_list.release ();
1718	}
1719
1720	/* Normalize predicate chains in THIS. */
1721
1722	void
1723	predicate::normalize (gimple *use_or_def, bool is_use)
1724	{
1725	if (dump_file && dump_flags & TDF_DETAILS)
1726	{
1727	fprintf (stream: dump_file, format: "Before normalization ");
1728	dump (dump_file, use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
1729	}
1730
1731	predicate norm_preds (empty_val ());
1732	for (unsigned i = 0; i < m_preds.length (); i++)
1733	{
1734	if (m_preds[i].length () != 1)
1735	norm_preds.normalize (chain: m_preds[i]);
1736	else
1737	norm_preds.normalize (pred: m_preds[i][0]);
1738	}
1739
1740	*this = norm_preds;
1741
1742	if (dump_file)
1743	{
1744	fprintf (stream: dump_file, format: "After normalization ");
1745	dump (dump_file, use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
1746	}
1747	}
1748
1749	/* Convert the chains of control dependence edges into a set of predicates.
1750	A control dependence chain is represented by a vector edges. DEP_CHAINS
1751	points to an array of NUM_CHAINS dependence chains. One edge in
1752	a dependence chain is mapped to predicate expression represented by
1753	pred_info type. One dependence chain is converted to a composite
1754	predicate that is the result of AND operation of pred_info mapped to
1755	each edge. A composite predicate is represented by a vector of
1756	pred_info. Sets M_PREDS to the resulting composite predicates. */
1757
1758	void
1759	predicate::init_from_control_deps (const vec<edge> *dep_chains,
1760	unsigned num_chains, bool is_use)
1761	{
1762	gcc_assert (is_empty ());
1763
1764	if (num_chains == 0)
1765	return;
1766
1767	if (DEBUG_PREDICATE_ANALYZER && dump_file)
1768	fprintf (stream: dump_file, format: "init_from_control_deps [%s] {%s}:\n",
1769	is_use ? "USE" : "DEF",
1770	format_edge_vecs (eva: dep_chains, n: num_chains).c_str ());
1771
1772	/* Convert the control dependency chain into a set of predicates. */
1773	m_preds.reserve (nelems: num_chains);
1774
1775	for (unsigned i = 0; i < num_chains; i++)
1776	{
1777	/* One path through the CFG represents a logical conjunction
1778	of the predicates. */
1779	const vec<edge> &path = dep_chains[i];
1780
1781	bool has_valid_pred = false;
1782	/* The chain of predicates guarding the definition along this path. */
1783	pred_chain t_chain{ };
1784	for (unsigned j = 0; j < path.length (); j++)
1785	{
1786	edge e = path[j];
1787	basic_block guard_bb = e->src;
1788
1789	gcc_assert (!empty_block_p (guard_bb) && !single_succ_p (guard_bb));
1790
1791	/* Skip this edge if it is bypassing an abort - when the
1792	condition is not satisfied we are neither reaching the
1793	definition nor the use so it isn't meaningful. Note if
1794	we are processing the use predicate the condition is
1795	meaningful. See PR65244. */
1796	if (!is_use && EDGE_COUNT (e->src->succs) == 2)
1797	{
1798	edge e1;
1799	edge_iterator ei1;
1800	bool skip = false;
1801
1802	FOR_EACH_EDGE (e1, ei1, e->src->succs)
1803	{
1804	if (EDGE_COUNT (e1->dest->succs) == 0)
1805	{
1806	skip = true;
1807	break;
1808	}
1809	}
1810	if (skip)
1811	{
1812	has_valid_pred = true;
1813	continue;
1814	}
1815	}
1816	/* Get the conditional controlling the bb exit edge. */
1817	gimple *cond_stmt = *gsi_last_bb (bb: guard_bb);
1818	if (gimple_code (g: cond_stmt) == GIMPLE_COND)
1819	{
1820	/* The true edge corresponds to the uninteresting condition.
1821	Add the negated predicate(s) for the edge to record
1822	the interesting condition. */
1823	pred_info one_pred;
1824	one_pred.pred_lhs = gimple_cond_lhs (gs: cond_stmt);
1825	one_pred.pred_rhs = gimple_cond_rhs (gs: cond_stmt);
1826	one_pred.cond_code = gimple_cond_code (gs: cond_stmt);
1827	one_pred.invert = !!(e->flags & EDGE_FALSE_VALUE);
1828
1829	t_chain.safe_push (obj: one_pred);
1830
1831	if (DEBUG_PREDICATE_ANALYZER && dump_file)
1832	{
1833	fprintf (stream: dump_file, format: "%d -> %d: one_pred = ",
1834	e->src->index, e->dest->index);
1835	dump_pred_info (f: dump_file, pred: one_pred);
1836	fputc (c: '\n', stream: dump_file);
1837	}
1838
1839	has_valid_pred = true;
1840	}
1841	else if (gswitch *gs = dyn_cast<gswitch *> (p: cond_stmt))
1842	{
1843	/* Find the case label, but avoid quadratic behavior. */
1844	tree l = get_cases_for_edge (e, gs);
1845	/* If more than one label reaches this block or the case
1846	label doesn't have a contiguous range of values (like the
1847	default one) fail. */
1848	if (!l || CASE_CHAIN (l) || !CASE_LOW (l))
1849	has_valid_pred = false;
1850	else if (!CASE_HIGH (l)
1851	|| operand_equal_p (CASE_LOW (l), CASE_HIGH (l)))
1852	{
1853	pred_info one_pred;
1854	one_pred.pred_lhs = gimple_switch_index (gs);
1855	one_pred.pred_rhs = CASE_LOW (l);
1856	one_pred.cond_code = EQ_EXPR;
1857	one_pred.invert = false;
1858	t_chain.safe_push (obj: one_pred);
1859	has_valid_pred = true;
1860	}
1861	else
1862	{
1863	/* Support a case label with a range with
1864	two predicates. We're overcommitting on
1865	the MAX_CHAIN_LEN budget by at most a factor
1866	of two here. */
1867	pred_info one_pred;
1868	one_pred.pred_lhs = gimple_switch_index (gs);
1869	one_pred.pred_rhs = CASE_LOW (l);
1870	one_pred.cond_code = GE_EXPR;
1871	one_pred.invert = false;
1872	t_chain.safe_push (obj: one_pred);
1873	one_pred.pred_rhs = CASE_HIGH (l);
1874	one_pred.cond_code = LE_EXPR;
1875	t_chain.safe_push (obj: one_pred);
1876	has_valid_pred = true;
1877	}
1878	}
1879	else if (stmt_can_throw_internal (cfun, cond_stmt)
1880	&& !(e->flags & EDGE_EH))
1881	/* Ignore the exceptional control flow and proceed as if
1882	E were a fallthru without a controlling predicate for
1883	both the USE (valid) and DEF (questionable) case. */
1884	has_valid_pred = true;
1885	else
1886	has_valid_pred = false;
1887
1888	/* For USE predicates we can drop components of the
1889	AND chain. */
1890	if (!has_valid_pred && !is_use)
1891	break;
1892	}
1893
1894	/* For DEF predicates we have to drop components of the OR chain
1895	on failure. */
1896	if (!has_valid_pred && !is_use)
1897	{
1898	t_chain.release ();
1899	continue;
1900	}
1901
1902	/* When we add || 1 simply prune the chain and return. */
1903	if (t_chain.is_empty ())
1904	{
1905	t_chain.release ();
1906	for (auto chain : m_preds)
1907	chain.release ();
1908	m_preds.truncate (size: 0);
1909	break;
1910	}
1911
1912	m_preds.quick_push (obj: t_chain);
1913	}
1914
1915	if (DEBUG_PREDICATE_ANALYZER && dump_file)
1916	dump (dump_file);
1917	}
1918
1919	/* Store a PRED in *THIS. */
1920
1921	void
1922	predicate::push_pred (const pred_info &pred)
1923	{
1924	pred_chain chain = vNULL;
1925	chain.safe_push (obj: pred);
1926	m_preds.safe_push (obj: chain);
1927	}
1928
1929	/* Dump predicates in *THIS to F. */
1930
1931	void
1932	predicate::dump (FILE *f) const
1933	{
1934	unsigned np = m_preds.length ();
1935	if (np == 0)
1936	{
1937	fprintf (stream: f, format: "\tTRUE (empty)\n");
1938	return;
1939	}
1940
1941	for (unsigned i = 0; i < np; i++)
1942	{
1943	if (i > 0)
1944	fprintf (stream: f, format: "\tOR (");
1945	else
1946	fprintf (stream: f, format: "\t(");
1947	dump_pred_chain (f, chain: m_preds[i]);
1948	fprintf (stream: f, format: ")\n");
1949	}
1950	}
1951
1952	/* Dump predicates in *THIS to stderr. */
1953
1954	void
1955	predicate::debug () const
1956	{
1957	dump (stderr);
1958	}
1959
1960	/* Dump predicates in *THIS for STMT prepended by MSG to F. */
1961
1962	void
1963	predicate::dump (FILE *f, gimple *stmt, const char *msg) const
1964	{
1965	fprintf (stream: f, format: "%s", msg);
1966	if (stmt)
1967	{
1968	fputc (c: '\t', stream: f);
1969	print_gimple_stmt (f, stmt, 0);
1970	fprintf (stream: f, format: " is conditional on:\n");
1971	}
1972
1973	dump (f);
1974	}
1975
1976	/* Initialize USE_PREDS with the predicates of the control dependence chains
1977	between the basic block DEF_BB that defines a variable of interst and
1978	USE_BB that uses the variable, respectively. */
1979
1980	bool
1981	uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_bb,
1982	basic_block use_bb)
1983	{
1984	if (DEBUG_PREDICATE_ANALYZER && dump_file)
1985	fprintf (stream: dump_file, format: "init_use_preds (def_bb = %u, use_bb = %u)\n",
1986	def_bb->index, use_bb->index);
1987
1988	gcc_assert (use_preds.is_empty ()
1989	&& dominated_by_p (CDI_DOMINATORS, use_bb, def_bb));
1990
1991	/* Set CD_ROOT to the basic block closest to USE_BB that is the control
1992	equivalent of (is guarded by the same predicate as) DEF_BB that also
1993	dominates USE_BB. This mimics the inner loop in
1994	compute_control_dep_chain. */
1995	basic_block cd_root = def_bb;
1996	do
1997	{
1998	basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, cd_root);
1999
2000	/* Stop at a loop exit which is also postdominating cd_root. */
2001	if (single_pred_p (bb: pdom) && !single_succ_p (bb: cd_root))
2002	break;
2003
2004	if (!dominated_by_p (CDI_DOMINATORS, pdom, cd_root)
2005	|| !dominated_by_p (CDI_DOMINATORS, use_bb, pdom))
2006	break;
2007
2008	cd_root = pdom;
2009	}
2010	while (1);
2011
2012	auto_bb_flag in_region (cfun);
2013	auto_vec<basic_block, 20> region (MIN (n_basic_blocks_for_fn (cfun),
2014	param_uninit_control_dep_attempts));
2015
2016	/* Set DEP_CHAINS to the set of edges between CD_ROOT and USE_BB.
2017	Each DEP_CHAINS element is a series of edges whose conditions
2018	are logical conjunctions. Together, the DEP_CHAINS vector is
2019	used below to initialize an OR expression of the conjunctions. */
2020	unsigned num_chains = 0;
2021	auto_vec<edge> *dep_chains = new auto_vec<edge>[MAX_NUM_CHAINS];
2022
2023	if (!dfs_mark_dominating_region (exit_src: use_bb, dom: cd_root, flag: in_region, bbs&: region)
2024	|| !compute_control_dep_chain (dom_bb: cd_root, dep_bb: use_bb, cd_chains: dep_chains, num_chains: &num_chains,
2025	in_region))
2026	{
2027	/* If the info in dep_chains is not complete we need to use a
2028	conservative approximation for the use predicate. */
2029	if (DEBUG_PREDICATE_ANALYZER && dump_file)
2030	fprintf (stream: dump_file, format: "init_use_preds: dep_chain incomplete, using "
2031	"conservative approximation\n");
2032	num_chains = 1;
2033	dep_chains[0].truncate (size: 0);
2034	simple_control_dep_chain (chain&: dep_chains[0], from: cd_root, to: use_bb);
2035	}
2036
2037	/* Unmark the region. */
2038	for (auto bb : region)
2039	bb->flags &= ~in_region;
2040
2041	/* From the set of edges computed above initialize *THIS as the OR
2042	condition under which the definition in DEF_BB is used in USE_BB.
2043	Each OR subexpression is represented by one element of DEP_CHAINS,
2044	where each element consists of a series of AND subexpressions. */
2045	use_preds.init_from_control_deps (dep_chains, num_chains, is_use: true);
2046	delete[] dep_chains;
2047	return !use_preds.is_empty ();
2048	}
2049
2050	/* Release resources in *THIS. */
2051
2052	predicate::~predicate ()
2053	{
2054	unsigned n = m_preds.length ();
2055	for (unsigned i = 0; i != n; ++i)
2056	m_preds[i].release ();
2057	m_preds.release ();
2058	}
2059
2060	/* Copy-assign RHS to *THIS. */
2061
2062	predicate&
2063	predicate::operator= (const predicate &rhs)
2064	{
2065	if (this == &rhs)
2066	return *this;
2067
2068	m_cval = rhs.m_cval;
2069
2070	unsigned n = m_preds.length ();
2071	for (unsigned i = 0; i != n; ++i)
2072	m_preds[i].release ();
2073	m_preds.release ();
2074
2075	n = rhs.m_preds.length ();
2076	for (unsigned i = 0; i != n; ++i)
2077	{
2078	const pred_chain &chain = rhs.m_preds[i];
2079	m_preds.safe_push (obj: chain.copy ());
2080	}
2081
2082	return *this;
2083	}
2084
2085	/* For each use edge of PHI, compute all control dependence chains
2086	and convert those to the composite predicates in M_PREDS.
2087	Return true if a nonempty predicate has been obtained. */
2088
2089	bool
2090	uninit_analysis::init_from_phi_def (gphi *phi)
2091	{
2092	gcc_assert (m_phi_def_preds.is_empty ());
2093
2094	basic_block phi_bb = gimple_bb (g: phi);
2095	/* Find the closest dominating bb to be the control dependence root. */
2096	basic_block cd_root = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
2097	if (!cd_root)
2098	return false;
2099
2100	/* Set DEF_EDGES to the edges to the PHI from the bb's that provide
2101	definitions of each of the PHI operands for which M_EVAL is false. */
2102	auto_vec<edge> def_edges;
2103	hash_set<gimple *> visited_phis;
2104	collect_phi_def_edges (phi, cd_root, edges: &def_edges, visited: &visited_phis);
2105
2106	unsigned nedges = def_edges.length ();
2107	if (nedges == 0)
2108	return false;
2109
2110	auto_bb_flag in_region (cfun);
2111	auto_vec<basic_block, 20> region (MIN (n_basic_blocks_for_fn (cfun),
2112	param_uninit_control_dep_attempts));
2113	/* Pre-mark the PHI incoming edges PHI block to make sure we only walk
2114	interesting edges from there. */
2115	for (unsigned i = 0; i < nedges; i++)
2116	{
2117	if (!(def_edges[i]->dest->flags & in_region))
2118	{
2119	if (!region.space (nelems: 1))
2120	break;
2121	def_edges[i]->dest->flags |= in_region;
2122	region.quick_push (obj: def_edges[i]->dest);
2123	}
2124	}
2125	for (unsigned i = 0; i < nedges; i++)
2126	if (!dfs_mark_dominating_region (exit_src: def_edges[i]->src, dom: cd_root,
2127	flag: in_region, bbs&: region))
2128	break;
2129
2130	unsigned num_chains = 0;
2131	auto_vec<edge> *dep_chains = new auto_vec<edge>[MAX_NUM_CHAINS];
2132	for (unsigned i = 0; i < nedges; i++)
2133	{
2134	edge e = def_edges[i];
2135	unsigned prev_nc = num_chains;
2136	bool complete_p = compute_control_dep_chain (dom_bb: cd_root, dep_bb: e->src, cd_chains: dep_chains,
2137	num_chains: &num_chains, in_region);
2138
2139	/* Update the newly added chains with the phi operand edge. */
2140	if (EDGE_COUNT (e->src->succs) > 1)
2141	{
2142	if (complete_p
2143	&& prev_nc == num_chains
2144	&& num_chains < MAX_NUM_CHAINS)
2145	/* We can only add a chain for the PHI operand edge when the
2146	collected info was complete, otherwise the predicate may
2147	not be conservative. */
2148	dep_chains[num_chains++] = vNULL;
2149	for (unsigned j = prev_nc; j < num_chains; j++)
2150	dep_chains[j].safe_push (obj: e);
2151	}
2152	}
2153
2154	/* Unmark the region. */
2155	for (auto bb : region)
2156	bb->flags &= ~in_region;
2157
2158	/* Convert control dependence chains to the predicate in *THIS under
2159	which the PHI operands are defined to values for which M_EVAL is
2160	false. */
2161	m_phi_def_preds.init_from_control_deps (dep_chains, num_chains, is_use: false);
2162	delete[] dep_chains;
2163	return !m_phi_def_preds.is_empty ();
2164	}
2165
2166	/* Compute the predicates that guard the use USE_STMT and check if
2167	the incoming paths that have an empty (or possibly empty) definition
2168	can be pruned. Return true if it can be determined that the use of
2169	PHI's def in USE_STMT is guarded by a predicate set that does not
2170	overlap with the predicate sets of all runtime paths that do not
2171	have a definition.
2172
2173	Return false if the use is not guarded or if it cannot be determined.
2174	USE_BB is the bb of the use (for phi operand use, the bb is not the bb
2175	of the phi stmt, but the source bb of the operand edge).
2176
2177	OPNDS is a bitmap with a bit set for each PHI operand of interest.
2178
2179	THIS->M_PREDS contains the (memoized) defining predicate chains of
2180	a PHI. If THIS->M_PREDS is empty, the PHI's defining predicate
2181	chains are computed and stored into THIS->M_PREDS as needed.
2182
2183	VISITED_PHIS is a pointer set of phis being visited. */
2184
2185	bool
2186	uninit_analysis::is_use_guarded (gimple *use_stmt, basic_block use_bb,
2187	gphi *phi, unsigned opnds,
2188	hash_set<gphi *> *visited)
2189	{
2190	if (visited->add (k: phi))
2191	return false;
2192
2193	/* The basic block where the PHI is defined. */
2194	basic_block def_bb = gimple_bb (g: phi);
2195
2196	/* Try to build the predicate expression under which the PHI flows
2197	into its use. This will be empty if the PHI is defined and used
2198	in the same bb. */
2199	predicate use_preds (true);
2200	if (!init_use_preds (use_preds, def_bb, use_bb))
2201	return false;
2202
2203	use_preds.simplify (use_or_def: use_stmt, /*is_use=*/true);
2204	use_preds.normalize (use_or_def: use_stmt, /*is_use=*/true);
2205	if (use_preds.is_false ())
2206	return true;
2207	if (use_preds.is_true ())
2208	return false;
2209
2210	/* Try to prune the dead incoming phi edges. */
2211	if (!overlap (phi, opnds, visited, use_preds))
2212	{
2213	if (DEBUG_PREDICATE_ANALYZER && dump_file)
2214	fputs (s: "found predicate overlap\n", stream: dump_file);
2215
2216	return true;
2217	}
2218
2219	if (m_phi_def_preds.is_empty ())
2220	{
2221	/* Lazily initialize *THIS from PHI. */
2222	if (!init_from_phi_def (phi))
2223	return false;
2224
2225	m_phi_def_preds.simplify (use_or_def: phi);
2226	m_phi_def_preds.normalize (use_or_def: phi);
2227	if (m_phi_def_preds.is_false ())
2228	return false;
2229	if (m_phi_def_preds.is_true ())
2230	return true;
2231	}
2232
2233	/* Return true if the predicate guarding the valid definition (i.e.,
2234	*THIS) is a superset of the predicate guarding the use (i.e.,
2235	USE_PREDS). */
2236	if (m_phi_def_preds.superset_of (preds: use_preds))
2237	return true;
2238
2239	return false;
2240	}
2241
2242	/* Public interface to the above. */
2243
2244	bool
2245	uninit_analysis::is_use_guarded (gimple *stmt, basic_block use_bb, gphi *phi,
2246	unsigned opnds)
2247	{
2248	hash_set<gphi *> visited;
2249	return is_use_guarded (use_stmt: stmt, use_bb, phi, opnds, visited: &visited);
2250	}
2251
2252