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