1	/* Gimple range GORI functions.
2	Copyright (C) 2017-2023 Free Software Foundation, Inc.
3	Contributed by Andrew MacLeod <amacleod@redhat.com>
4	and Aldy Hernandez <aldyh@redhat.com>.
5
6	This file is part of GCC.
7
8	GCC is free software; you can redistribute it and/or modify
9	it under the terms of the GNU General Public License as published by
10	the Free Software Foundation; either version 3, or (at your option)
11	any later version.
12
13	GCC is distributed in the hope that it will be useful,
14	but WITHOUT ANY WARRANTY; without even the implied warranty of
15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16	GNU General Public License for more details.
17
18	You should have received a copy of the GNU General Public License
19	along with GCC; see the file COPYING3. If not see
20	<http://www.gnu.org/licenses/>. */
21
22	#include "config.h"
23	#include "system.h"
24	#include "coretypes.h"
25	#include "backend.h"
26	#include "tree.h"
27	#include "gimple.h"
28	#include "ssa.h"
29	#include "gimple-pretty-print.h"
30	#include "gimple-range.h"
31
32	// Return TRUE if GS is a logical && or || expression.
33
34	static inline bool
35	is_gimple_logical_p (const gimple *gs)
36	{
37	// Look for boolean and/or condition.
38	if (is_gimple_assign (gs))
39	switch (gimple_expr_code (stmt: gs))
40	{
41	case TRUTH_AND_EXPR:
42	case TRUTH_OR_EXPR:
43	return true;
44
45	case BIT_AND_EXPR:
46	case BIT_IOR_EXPR:
47	// Bitwise operations on single bits are logical too.
48	if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs)),
49	boolean_type_node))
50	return true;
51	break;
52
53	default:
54	break;
55	}
56	return false;
57	}
58
59	/* RANGE_DEF_CHAIN is used to determine which SSA names in a block can
60	have range information calculated for them, and what the
61	dependencies on each other are.
62
63	Information for a basic block is calculated once and stored. It is
64	only calculated the first time a query is made, so if no queries
65	are made, there is little overhead.
66
67	The def_chain bitmap is indexed by SSA_NAME_VERSION. Bits are set
68	within this bitmap to indicate SSA names that are defined in the
69	SAME block and used to calculate this SSA name.
70
71
72	<bb 2> :
73	_1 = x_4(D) + -2;
74	_2 = _1 * 4;
75	j_7 = foo ();
76	q_5 = _2 + 3;
77	if (q_5 <= 13)
78
79	_1 : x_4(D)
80	_2 : 1 x_4(D)
81	q_5 : _1 _2 x_4(D)
82
83	This dump indicates the bits set in the def_chain vector.
84	as well as demonstrates the def_chain bits for the related ssa_names.
85
86	Checking the chain for _2 indicates that _1 and x_4 are used in
87	its evaluation.
88
89	Def chains also only include statements which are valid gimple
90	so a def chain will only span statements for which the range
91	engine implements operations for. */
92
93
94	// Construct a range_def_chain.
95
96	range_def_chain::range_def_chain ()
97	{
98	bitmap_obstack_initialize (&m_bitmaps);
99	m_def_chain.create (nelems: 0);
100	m_def_chain.safe_grow_cleared (num_ssa_names);
101	m_logical_depth = 0;
102	}
103
104	// Destruct a range_def_chain.
105
106	range_def_chain::~range_def_chain ()
107	{
108	m_def_chain.release ();
109	bitmap_obstack_release (&m_bitmaps);
110	}
111
112	// Return true if NAME is in the def chain of DEF. If BB is provided,
113	// only return true if the defining statement of DEF is in BB.
114
115	bool
116	range_def_chain::in_chain_p (tree name, tree def)
117	{
118	gcc_checking_assert (gimple_range_ssa_p (def));
119	gcc_checking_assert (gimple_range_ssa_p (name));
120
121	// Get the definition chain for DEF.
122	bitmap chain = get_def_chain (name: def);
123
124	if (chain == NULL)
125	return false;
126	return bitmap_bit_p (chain, SSA_NAME_VERSION (name));
127	}
128
129	// Add either IMP or the import list B to the import set of DATA.
130
131	void
132	range_def_chain::set_import (struct rdc &data, tree imp, bitmap b)
133	{
134	// If there are no imports, just return
135	if (imp == NULL_TREE && !b)
136	return;
137	if (!data.m_import)
138	data.m_import = BITMAP_ALLOC (obstack: &m_bitmaps);
139	if (imp != NULL_TREE)
140	bitmap_set_bit (data.m_import, SSA_NAME_VERSION (imp));
141	else
142	bitmap_ior_into (data.m_import, b);
143	}
144
145	// Return the import list for NAME.
146
147	bitmap
148	range_def_chain::get_imports (tree name)
149	{
150	if (!has_def_chain (name))
151	get_def_chain (name);
152	bitmap i = m_def_chain[SSA_NAME_VERSION (name)].m_import;
153	return i;
154	}
155
156	// Return true if IMPORT is an import to NAMEs def chain.
157
158	bool
159	range_def_chain::chain_import_p (tree name, tree import)
160	{
161	bitmap b = get_imports (name);
162	if (b)
163	return bitmap_bit_p (b, SSA_NAME_VERSION (import));
164	return false;
165	}
166
167	// Build def_chains for NAME if it is in BB. Copy the def chain into RESULT.
168
169	void
170	range_def_chain::register_dependency (tree name, tree dep, basic_block bb)
171	{
172	if (!gimple_range_ssa_p (exp: dep))
173	return;
174
175	unsigned v = SSA_NAME_VERSION (name);
176	if (v >= m_def_chain.length ())
177	m_def_chain.safe_grow_cleared (num_ssa_names + 1);
178	struct rdc &src = m_def_chain[v];
179	gimple *def_stmt = SSA_NAME_DEF_STMT (dep);
180	unsigned dep_v = SSA_NAME_VERSION (dep);
181	bitmap b;
182
183	// Set the direct dependency cache entries.
184	if (!src.ssa1)
185	src.ssa1 = SSA_NAME_VERSION (dep);
186	else if (!src.ssa2 && src.ssa1 != SSA_NAME_VERSION (dep))
187	src.ssa2 = SSA_NAME_VERSION (dep);
188
189	// Don't calculate imports or export/dep chains if BB is not provided.
190	// This is usually the case for when the temporal cache wants the direct
191	// dependencies of a stmt.
192	if (!bb)
193	return;
194
195	if (!src.bm)
196	src.bm = BITMAP_ALLOC (obstack: &m_bitmaps);
197
198	// Add this operand into the result.
199	bitmap_set_bit (src.bm, dep_v);
200
201	if (gimple_bb (g: def_stmt) == bb && !is_a<gphi *>(p: def_stmt))
202	{
203	// Get the def chain for the operand.
204	b = get_def_chain (name: dep);
205	// If there was one, copy it into result. Access def_chain directly
206	// as the get_def_chain request above could reallocate the vector.
207	if (b)
208	bitmap_ior_into (m_def_chain[v].bm, b);
209	// And copy the import list.
210	set_import (data&: m_def_chain[v], NULL_TREE, b: get_imports (name: dep));
211	}
212	else
213	// Originated outside the block, so it is an import.
214	set_import (data&: src, imp: dep, NULL);
215	}
216
217	bool
218	range_def_chain::def_chain_in_bitmap_p (tree name, bitmap b)
219	{
220	bitmap a = get_def_chain (name);
221	if (a && b)
222	return bitmap_intersect_p (a, b);
223	return false;
224	}
225
226	void
227	range_def_chain::add_def_chain_to_bitmap (bitmap b, tree name)
228	{
229	bitmap r = get_def_chain (name);
230	if (r)
231	bitmap_ior_into (b, r);
232	}
233
234
235	// Return TRUE if NAME has been processed for a def_chain.
236
237	inline bool
238	range_def_chain::has_def_chain (tree name)
239	{
240	// Ensure there is an entry in the internal vector.
241	unsigned v = SSA_NAME_VERSION (name);
242	if (v >= m_def_chain.length ())
243	m_def_chain.safe_grow_cleared (num_ssa_names + 1);
244	return (m_def_chain[v].ssa1 != 0);
245	}
246
247
248
249	// Calculate the def chain for NAME and all of its dependent
250	// operands. Only using names in the same BB. Return the bitmap of
251	// all names in the m_def_chain. This only works for supported range
252	// statements.
253
254	bitmap
255	range_def_chain::get_def_chain (tree name)
256	{
257	tree ssa[3];
258	unsigned v = SSA_NAME_VERSION (name);
259
260	// If it has already been processed, just return the cached value.
261	if (has_def_chain (name) && m_def_chain[v].bm)
262	return m_def_chain[v].bm;
263
264	// No definition chain for default defs.
265	if (SSA_NAME_IS_DEFAULT_DEF (name))
266	{
267	// A Default def is always an import.
268	set_import (data&: m_def_chain[v], imp: name, NULL);
269	return NULL;
270	}
271
272	gimple *stmt = SSA_NAME_DEF_STMT (name);
273	unsigned count = gimple_range_ssa_names (vec: ssa, vec_size: 3, stmt);
274	if (count == 0)
275	{
276	// Stmts not understood or with no operands are always imports.
277	set_import (data&: m_def_chain[v], imp: name, NULL);
278	return NULL;
279	}
280
281	// Terminate the def chains if we see too many cascading stmts.
282	if (m_logical_depth == param_ranger_logical_depth)
283	return NULL;
284
285	// Increase the depth if we have a pair of ssa-names.
286	if (count > 1)
287	m_logical_depth++;
288
289	for (unsigned x = 0; x < count; x++)
290	register_dependency (name, dep: ssa[x], bb: gimple_bb (g: stmt));
291
292	if (count > 1)
293	m_logical_depth--;
294
295	return m_def_chain[v].bm;
296	}
297
298	// Dump what we know for basic block BB to file F.
299
300	void
301	range_def_chain::dump (FILE *f, basic_block bb, const char *prefix)
302	{
303	unsigned x, y;
304	bitmap_iterator bi;
305
306	// Dump the def chain for each SSA_NAME defined in BB.
307	for (x = 1; x < num_ssa_names; x++)
308	{
309	tree name = ssa_name (x);
310	if (!name)
311	continue;
312	gimple *stmt = SSA_NAME_DEF_STMT (name);
313	if (!stmt || (bb && gimple_bb (g: stmt) != bb))
314	continue;
315	bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL);
316	if (chain && !bitmap_empty_p (map: chain))
317	{
318	fprintf (stream: f, format: prefix);
319	print_generic_expr (f, name, TDF_SLIM);
320	fprintf (stream: f, format: " : ");
321
322	bitmap imports = get_imports (name);
323	EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi)
324	{
325	print_generic_expr (f, ssa_name (y), TDF_SLIM);
326	if (imports && bitmap_bit_p (imports, y))
327	fprintf (stream: f, format: "(I)");
328	fprintf (stream: f, format: " ");
329	}
330	fprintf (stream: f, format: "\n");
331	}
332	}
333	}
334
335
336	// -------------------------------------------------------------------
337
338	/* GORI_MAP is used to accumulate what SSA names in a block can
339	generate range information, and provides tools for the block ranger
340	to enable it to efficiently calculate these ranges.
341
342	GORI stands for "Generates Outgoing Range Information."
343
344	It utilizes the range_def_chain class to construct def_chains.
345	Information for a basic block is calculated once and stored. It is
346	only calculated the first time a query is made. If no queries are
347	made, there is little overhead.
348
349	one bitmap is maintained for each basic block:
350	m_outgoing : a set bit indicates a range can be generated for a name.
351
352	Generally speaking, the m_outgoing vector is the union of the
353	entire def_chain of all SSA names used in the last statement of the
354	block which generate ranges. */
355
356
357	// Initialize a gori-map structure.
358
359	gori_map::gori_map ()
360	{
361	m_outgoing.create (nelems: 0);
362	m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
363	m_incoming.create (nelems: 0);
364	m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
365	m_maybe_variant = BITMAP_ALLOC (obstack: &m_bitmaps);
366	}
367
368	// Free any memory the GORI map allocated.
369
370	gori_map::~gori_map ()
371	{
372	m_incoming.release ();
373	m_outgoing.release ();
374	}
375
376	// Return the bitmap vector of all export from BB. Calculate if necessary.
377
378	bitmap
379	gori_map::exports (basic_block bb)
380	{
381	if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
382	calculate_gori (bb);
383	return m_outgoing[bb->index];
384	}
385
386	// Return the bitmap vector of all imports to BB. Calculate if necessary.
387
388	bitmap
389	gori_map::imports (basic_block bb)
390	{
391	if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
392	calculate_gori (bb);
393	return m_incoming[bb->index];
394	}
395
396	// Return true if NAME is can have ranges generated for it from basic
397	// block BB.
398
399	bool
400	gori_map::is_export_p (tree name, basic_block bb)
401	{
402	// If no BB is specified, test if it is exported anywhere in the IL.
403	if (!bb)
404	return bitmap_bit_p (m_maybe_variant, SSA_NAME_VERSION (name));
405	return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name));
406	}
407
408	// Set or clear the m_maybe_variant bit to determine if ranges will be tracked
409	// for NAME. A clear bit means they will NOT be tracked.
410
411	void
412	gori_map::set_range_invariant (tree name, bool invariant)
413	{
414	if (invariant)
415	bitmap_clear_bit (m_maybe_variant, SSA_NAME_VERSION (name));
416	else
417	bitmap_set_bit (m_maybe_variant, SSA_NAME_VERSION (name));
418	}
419
420	// Return true if NAME is an import to block BB.
421
422	bool
423	gori_map::is_import_p (tree name, basic_block bb)
424	{
425	// If no BB is specified, test if it is exported anywhere in the IL.
426	return bitmap_bit_p (imports (bb), SSA_NAME_VERSION (name));
427	}
428
429	// If NAME is non-NULL and defined in block BB, calculate the def
430	// chain and add it to m_outgoing.
431
432	void
433	gori_map::maybe_add_gori (tree name, basic_block bb)
434	{
435	if (name)
436	{
437	// Check if there is a def chain, regardless of the block.
438	add_def_chain_to_bitmap (b: m_outgoing[bb->index], name);
439	// Check for any imports.
440	bitmap imp = get_imports (name);
441	// If there were imports, add them so we can recompute
442	if (imp)
443	bitmap_ior_into (m_incoming[bb->index], imp);
444	// This name is always an import.
445	if (gimple_bb (SSA_NAME_DEF_STMT (name)) != bb)
446	bitmap_set_bit (m_incoming[bb->index], SSA_NAME_VERSION (name));
447
448	// Def chain doesn't include itself, and even if there isn't a
449	// def chain, this name should be added to exports.
450	bitmap_set_bit (m_outgoing[bb->index], SSA_NAME_VERSION (name));
451	}
452	}
453
454	// Calculate all the required information for BB.
455
456	void
457	gori_map::calculate_gori (basic_block bb)
458	{
459	tree name;
460	if (bb->index >= (signed int)m_outgoing.length ())
461	{
462	m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
463	m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
464	}
465	gcc_checking_assert (m_outgoing[bb->index] == NULL);
466	m_outgoing[bb->index] = BITMAP_ALLOC (obstack: &m_bitmaps);
467	m_incoming[bb->index] = BITMAP_ALLOC (obstack: &m_bitmaps);
468
469	if (single_succ_p (bb))
470	return;
471
472	// If this block's last statement may generate range information, go
473	// calculate it.
474	gimple *stmt = gimple_outgoing_range_stmt_p (bb);
475	if (!stmt)
476	return;
477	if (is_a<gcond *> (p: stmt))
478	{
479	gcond *gc = as_a<gcond *>(p: stmt);
480	name = gimple_range_ssa_p (exp: gimple_cond_lhs (gs: gc));
481	maybe_add_gori (name, bb: gimple_bb (g: stmt));
482
483	name = gimple_range_ssa_p (exp: gimple_cond_rhs (gs: gc));
484	maybe_add_gori (name, bb: gimple_bb (g: stmt));
485	}
486	else
487	{
488	// Do not process switches if they are too large.
489	if (EDGE_COUNT (bb->succs) > (unsigned)param_vrp_switch_limit)
490	return;
491	gswitch *gs = as_a<gswitch *>(p: stmt);
492	name = gimple_range_ssa_p (exp: gimple_switch_index (gs));
493	maybe_add_gori (name, bb: gimple_bb (g: stmt));
494	}
495	// Add this bitmap to the aggregate list of all outgoing names.
496	bitmap_ior_into (m_maybe_variant, m_outgoing[bb->index]);
497	}
498
499	// Dump the table information for BB to file F.
500
501	void
502	gori_map::dump (FILE *f, basic_block bb, bool verbose)
503	{
504	// BB was not processed.
505	if (!m_outgoing[bb->index] || bitmap_empty_p (map: m_outgoing[bb->index]))
506	return;
507
508	tree name;
509
510	bitmap imp = imports (bb);
511	if (!bitmap_empty_p (map: imp))
512	{
513	if (verbose)
514	fprintf (stream: f, format: "bb<%u> Imports: ",bb->index);
515	else
516	fprintf (stream: f, format: "Imports: ");
517	FOR_EACH_GORI_IMPORT_NAME (*this, bb, name)
518	{
519	print_generic_expr (f, name, TDF_SLIM);
520	fprintf (stream: f, format: " ");
521	}
522	fputc (c: '\n', stream: f);
523	}
524
525	if (verbose)
526	fprintf (stream: f, format: "bb<%u> Exports: ",bb->index);
527	else
528	fprintf (stream: f, format: "Exports: ");
529	// Dump the export vector.
530	FOR_EACH_GORI_EXPORT_NAME (*this, bb, name)
531	{
532	print_generic_expr (f, name, TDF_SLIM);
533	fprintf (stream: f, format: " ");
534	}
535	fputc (c: '\n', stream: f);
536
537	range_def_chain::dump (f, bb, prefix: " ");
538	}
539
540	// Dump the entire GORI map structure to file F.
541
542	void
543	gori_map::dump (FILE *f)
544	{
545	basic_block bb;
546	FOR_EACH_BB_FN (bb, cfun)
547	dump (f, bb);
548	}
549
550	DEBUG_FUNCTION void
551	debug (gori_map &g)
552	{
553	g.dump (stderr);
554	}
555
556	// -------------------------------------------------------------------
557
558	// Construct a gori_compute object.
559
560	gori_compute::gori_compute (int not_executable_flag)
561	: outgoing (param_vrp_switch_limit), tracer ("GORI ")
562	{
563	m_not_executable_flag = not_executable_flag;
564	// Create a boolean_type true and false range.
565	m_bool_zero = range_false ();
566	m_bool_one = range_true ();
567	if (dump_file && (param_ranger_debug & RANGER_DEBUG_GORI))
568	tracer.enable_trace ();
569	}
570
571	// Given the switch S, return an evaluation in R for NAME when the lhs
572	// evaluates to LHS. Returning false means the name being looked for
573	// was not resolvable.
574
575	bool
576	gori_compute::compute_operand_range_switch (vrange &r, gswitch *s,
577	const vrange &lhs,
578	tree name, fur_source &src)
579	{
580	tree op1 = gimple_switch_index (gs: s);
581
582	// If name matches, the range is simply the range from the edge.
583	// Empty ranges are viral as they are on a path which isn't
584	// executable.
585	if (op1 == name || lhs.undefined_p ())
586	{
587	r = lhs;
588	return true;
589	}
590
591	// If op1 is in the definition chain, pass lhs back.
592	if (gimple_range_ssa_p (exp: op1) && in_chain_p (name, def: op1))
593	return compute_operand_range (r, SSA_NAME_DEF_STMT (op1), lhs, name, src);
594
595	return false;
596	}
597
598
599	// Return an evaluation for NAME as it would appear in STMT when the
600	// statement's lhs evaluates to LHS. If successful, return TRUE and
601	// store the evaluation in R, otherwise return FALSE.
602
603	bool
604	gori_compute::compute_operand_range (vrange &r, gimple *stmt,
605	const vrange &lhs, tree name,
606	fur_source &src, value_relation *rel)
607	{
608	value_relation vrel;
609	value_relation *vrel_ptr = rel;
610	// Empty ranges are viral as they are on an unexecutable path.
611	if (lhs.undefined_p ())
612	{
613	r.set_undefined ();
614	return true;
615	}
616	if (is_a<gswitch *> (p: stmt))
617	return compute_operand_range_switch (r, s: as_a<gswitch *> (p: stmt), lhs, name,
618	src);
619	gimple_range_op_handler handler (stmt);
620	if (!handler)
621	return false;
622
623	tree op1 = gimple_range_ssa_p (exp: handler.operand1 ());
624	tree op2 = gimple_range_ssa_p (exp: handler.operand2 ());
625
626	// If there is a relation betwen op1 and op2, use it instead as it is
627	// likely to be more applicable.
628	if (op1 && op2)
629	{
630	Value_Range r1, r2;
631	r1.set_varying (TREE_TYPE (op1));
632	r2.set_varying (TREE_TYPE (op2));
633	relation_kind k = handler.op1_op2_relation (lhs, op1: r1, op2: r2);
634	if (k != VREL_VARYING)
635	{
636	vrel.set_relation (r: k, n1: op1, n2: op2);
637	vrel_ptr = &vrel;
638	}
639	}
640
641	// Handle end of lookup first.
642	if (op1 == name)
643	return compute_operand1_range (r, handler, lhs, src, rel: vrel_ptr);
644	if (op2 == name)
645	return compute_operand2_range (r, handler, lhs, src, rel: vrel_ptr);
646
647	// NAME is not in this stmt, but one of the names in it ought to be
648	// derived from it.
649	bool op1_in_chain = op1 && in_chain_p (name, def: op1);
650	bool op2_in_chain = op2 && in_chain_p (name, def: op2);
651
652	// If neither operand is derived, then this stmt tells us nothing.
653	if (!op1_in_chain && !op2_in_chain)
654	return false;
655
656	// If either operand is in the def chain of the other (or they are equal), it
657	// will be evaluated twice and can result in an exponential time calculation.
658	// Instead just evaluate the one operand.
659	if (op1_in_chain && op2_in_chain)
660	{
661	if (in_chain_p (name: op1, def: op2) || op1 == op2)
662	op1_in_chain = false;
663	else if (in_chain_p (name: op2, def: op1))
664	op2_in_chain = false;
665	}
666
667	bool res = false;
668	// If the lhs doesn't tell us anything only a relation can possibly enhance
669	// the result.
670	if (lhs.varying_p ())
671	{
672	if (!vrel_ptr)
673	return false;
674	// If there is a relation (ie: x != y) , it can only be relevant if
675	// a) both elements are in the defchain
676	// c = x > y // (x and y are in c's defchain)
677	if (op1_in_chain)
678	res = in_chain_p (name: vrel_ptr->op1 (), def: op1)
679	&& in_chain_p (name: vrel_ptr->op2 (), def: op1);
680	if (!res && op2_in_chain)
681	res = in_chain_p (name: vrel_ptr->op1 (), def: op2)
682	|| in_chain_p (name: vrel_ptr->op2 (), def: op2);
683	if (!res)
684	{
685	// or b) one relation element is in the defchain of the other and the
686	// other is the LHS of this stmt.
687	// x = y + 2
688	if (vrel_ptr->op1 () == handler.lhs ()
689	&& (vrel_ptr->op2 () == op1 || vrel_ptr->op2 () == op2))
690	res = true;
691	else if (vrel_ptr->op2 () == handler.lhs ()
692	&& (vrel_ptr->op1 () == op1 || vrel_ptr->op1 () == op2))
693	res = true;
694	}
695	if (!res)
696	return false;
697	}
698
699	// Process logicals as they have special handling.
700	if (is_gimple_logical_p (gs: stmt))
701	{
702	// If the lhs doesn't tell us anything, neither will combining operands.
703	if (lhs.varying_p ())
704	return false;
705
706	unsigned idx;
707	if ((idx = tracer.header (str: "compute_operand ")))
708	{
709	print_generic_expr (dump_file, name, TDF_SLIM);
710	fprintf (stream: dump_file, format: " with LHS = ");
711	lhs.dump (dump_file);
712	fprintf (stream: dump_file, format: " at stmt ");
713	print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
714	}
715
716	tree type = TREE_TYPE (name);
717	Value_Range op1_trange (type), op1_frange (type);
718	Value_Range op2_trange (type), op2_frange (type);
719	compute_logical_operands (true_range&: op1_trange, false_range&: op1_frange, handler,
720	lhs: as_a <irange> (v: lhs),
721	name, src, op: op1, op_in_chain: op1_in_chain);
722	compute_logical_operands (true_range&: op2_trange, false_range&: op2_frange, handler,
723	lhs: as_a <irange> (v: lhs),
724	name, src, op: op2, op_in_chain: op2_in_chain);
725	res = logical_combine (r,
726	code: gimple_expr_code (stmt),
727	lhs: as_a <irange> (v: lhs),
728	op1_true: op1_trange, op1_false: op1_frange, op2_true: op2_trange, op2_false: op2_frange);
729	if (idx)
730	tracer.trailer (counter: idx, caller: "compute_operand", result: res, name, r);
731	return res;
732	}
733	// Follow the appropriate operands now.
734	if (op1_in_chain && op2_in_chain)
735	return compute_operand1_and_operand2_range (r, handler, lhs, name, src,
736	rel: vrel_ptr);
737	Value_Range vr;
738	gimple *src_stmt;
739	if (op1_in_chain)
740	{
741	vr.set_type (TREE_TYPE (op1));
742	if (!compute_operand1_range (r&: vr, handler, lhs, src, rel: vrel_ptr))
743	return false;
744	src_stmt = SSA_NAME_DEF_STMT (op1);
745	}
746	else
747	{
748	gcc_checking_assert (op2_in_chain);
749	vr.set_type (TREE_TYPE (op2));
750	if (!compute_operand2_range (r&: vr, handler, lhs, src, rel: vrel_ptr))
751	return false;
752	src_stmt = SSA_NAME_DEF_STMT (op2);
753	}
754
755	gcc_checking_assert (src_stmt);
756	// Then feed this range back as the LHS of the defining statement.
757	return compute_operand_range (r, stmt: src_stmt, lhs: vr, name, src, rel: vrel_ptr);
758	// If neither operand is derived, this statement tells us nothing.
759	}
760
761
762	// Return TRUE if range R is either a true or false compatible range.
763
764	static bool
765	range_is_either_true_or_false (const irange &r)
766	{
767	if (r.undefined_p ())
768	return false;
769
770	// This is complicated by the fact that Ada has multi-bit booleans,
771	// so true can be ~[0, 0] (i.e. [1,MAX]).
772	tree type = r.type ();
773	gcc_checking_assert (range_compatible_p (type, boolean_type_node));
774	return (r.singleton_p ()
775	|| !r.contains_p (wi::zero (TYPE_PRECISION (type))));
776	}
777
778	// Evaluate a binary logical expression by combining the true and
779	// false ranges for each of the operands based on the result value in
780	// the LHS.
781
782	bool
783	gori_compute::logical_combine (vrange &r, enum tree_code code,
784	const irange &lhs,
785	const vrange &op1_true, const vrange &op1_false,
786	const vrange &op2_true, const vrange &op2_false)
787	{
788	if (op1_true.varying_p () && op1_false.varying_p ()
789	&& op2_true.varying_p () && op2_false.varying_p ())
790	return false;
791
792	unsigned idx;
793	if ((idx = tracer.header (str: "logical_combine")))
794	{
795	switch (code)
796	{
797	case TRUTH_OR_EXPR:
798	case BIT_IOR_EXPR:
799	fprintf (stream: dump_file, format: " || ");
800	break;
801	case TRUTH_AND_EXPR:
802	case BIT_AND_EXPR:
803	fprintf (stream: dump_file, format: " && ");
804	break;
805	default:
806	break;
807	}
808	fprintf (stream: dump_file, format: " with LHS = ");
809	lhs.dump (dump_file);
810	fputc (c: '\n', stream: dump_file);
811
812	tracer.print (counter: idx, str: "op1_true = ");
813	op1_true.dump (dump_file);
814	fprintf (stream: dump_file, format: " op1_false = ");
815	op1_false.dump (dump_file);
816	fputc (c: '\n', stream: dump_file);
817	tracer.print (counter: idx, str: "op2_true = ");
818	op2_true.dump (dump_file);
819	fprintf (stream: dump_file, format: " op2_false = ");
820	op2_false.dump (dump_file);
821	fputc (c: '\n', stream: dump_file);
822	}
823
824	// This is not a simple fold of a logical expression, rather it
825	// determines ranges which flow through the logical expression.
826	//
827	// Assuming x_8 is an unsigned char, and relational statements:
828	// b_1 = x_8 < 20
829	// b_2 = x_8 > 5
830	// consider the logical expression and branch:
831	// c_2 = b_1 && b_2
832	// if (c_2)
833	//
834	// To determine the range of x_8 on either edge of the branch, one
835	// must first determine what the range of x_8 is when the boolean
836	// values of b_1 and b_2 are both true and false.
837	// b_1 TRUE x_8 = [0, 19]
838	// b_1 FALSE x_8 = [20, 255]
839	// b_2 TRUE x_8 = [6, 255]
840	// b_2 FALSE x_8 = [0,5].
841	//
842	// These ranges are then combined based on the expected outcome of
843	// the branch. The range on the TRUE side of the branch must satisfy
844	// b_1 == true && b_2 == true
845	//
846	// In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255]
847	// must be true. The range of x_8 on the true side must be the
848	// intersection of both ranges since both must be true. Thus the
849	// range of x_8 on the true side is [6, 19].
850	//
851	// To determine the ranges on the FALSE side, all 3 combinations of
852	// failing ranges must be considered, and combined as any of them
853	// can cause the false result.
854	//
855	// If the LHS can be TRUE or FALSE, then evaluate both a TRUE and
856	// FALSE results and combine them. If we fell back to VARYING any
857	// range restrictions that have been discovered up to this point
858	// would be lost.
859	if (!range_is_either_true_or_false (r: lhs))
860	{
861	bool res;
862	Value_Range r1 (r);
863	if (logical_combine (r&: r1, code, lhs: m_bool_zero, op1_true, op1_false,
864	op2_true, op2_false)
865	&& logical_combine (r, code, lhs: m_bool_one, op1_true, op1_false,
866	op2_true, op2_false))
867	{
868	r.union_ (r1);
869	res = true;
870	}
871	else
872	res = false;
873	if (idx && res)
874	{
875	tracer.print (counter: idx, str: "logical_combine produced ");
876	r.dump (dump_file);
877	fputc (c: '\n', stream: dump_file);
878	}
879	return res;
880	}
881
882	switch (code)
883	{
884	// A logical AND combines ranges from 2 boolean conditions.
885	// c_2 = b_1 && b_2
886	case TRUTH_AND_EXPR:
887	case BIT_AND_EXPR:
888	if (!lhs.zero_p ())
889	{
890	// The TRUE side is the intersection of the 2 true ranges.
891	r = op1_true;
892	r.intersect (op2_true);
893	}
894	else
895	{
896	// The FALSE side is the union of the other 3 cases.
897	Value_Range ff (op1_false);
898	ff.intersect (r: op2_false);
899	Value_Range tf (op1_true);
900	tf.intersect (r: op2_false);
901	Value_Range ft (op1_false);
902	ft.intersect (r: op2_true);
903	r = ff;
904	r.union_ (tf);
905	r.union_ (ft);
906	}
907	break;
908	// A logical OR combines ranges from 2 boolean conditions.
909	// c_2 = b_1 || b_2
910	case TRUTH_OR_EXPR:
911	case BIT_IOR_EXPR:
912	if (lhs.zero_p ())
913	{
914	// An OR operation will only take the FALSE path if both
915	// operands are false simultaneously, which means they should
916	// be intersected. !(x || y) == !x && !y
917	r = op1_false;
918	r.intersect (op2_false);
919	}
920	else
921	{
922	// The TRUE side of an OR operation will be the union of
923	// the other three combinations.
924	Value_Range tt (op1_true);
925	tt.intersect (r: op2_true);
926	Value_Range tf (op1_true);
927	tf.intersect (r: op2_false);
928	Value_Range ft (op1_false);
929	ft.intersect (r: op2_true);
930	r = tt;
931	r.union_ (tf);
932	r.union_ (ft);
933	}
934	break;
935	default:
936	gcc_unreachable ();
937	}
938
939	if (idx)
940	tracer.trailer (counter: idx, caller: "logical_combine", result: true, NULL_TREE, r);
941	return true;
942	}
943
944
945	// Given a logical STMT, calculate true and false ranges for each
946	// potential path of NAME, assuming NAME came through the OP chain if
947	// OP_IN_CHAIN is true.
948
949	void
950	gori_compute::compute_logical_operands (vrange &true_range, vrange &false_range,
951	gimple_range_op_handler &handler,
952	const irange &lhs,
953	tree name, fur_source &src,
954	tree op, bool op_in_chain)
955	{
956	gimple *stmt = handler.stmt ();
957	gimple *src_stmt = gimple_range_ssa_p (exp: op) ? SSA_NAME_DEF_STMT (op) : NULL;
958	if (!op_in_chain || !src_stmt || chain_import_p (name: handler.lhs (), import: op))
959	{
960	// If op is not in the def chain, or defined in this block,
961	// use its known value on entry to the block.
962	src.get_operand (r&: true_range, expr: name);
963	false_range = true_range;
964	unsigned idx;
965	if ((idx = tracer.header (str: "logical_operand")))
966	{
967	print_generic_expr (dump_file, op, TDF_SLIM);
968	fprintf (stream: dump_file, format: " not in computation chain. Queried.\n");
969	tracer.trailer (counter: idx, caller: "logical_operand", result: true, NULL_TREE, r: true_range);
970	}
971	return;
972	}
973
974	enum tree_code code = gimple_expr_code (stmt);
975	// Optimize [0 = x | y], since neither operand can ever be non-zero.
976	if ((code == BIT_IOR_EXPR || code == TRUTH_OR_EXPR) && lhs.zero_p ())
977	{
978	if (!compute_operand_range (r&: false_range, stmt: src_stmt, lhs: m_bool_zero, name,
979	src))
980	src.get_operand (r&: false_range, expr: name);
981	true_range = false_range;
982	return;
983	}
984
985	// Optimize [1 = x & y], since neither operand can ever be zero.
986	if ((code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) && lhs == m_bool_one)
987	{
988	if (!compute_operand_range (r&: true_range, stmt: src_stmt, lhs: m_bool_one, name, src))
989	src.get_operand (r&: true_range, expr: name);
990	false_range = true_range;
991	return;
992	}
993
994	// Calculate ranges for true and false on both sides, since the false
995	// path is not always a simple inversion of the true side.
996	if (!compute_operand_range (r&: true_range, stmt: src_stmt, lhs: m_bool_one, name, src))
997	src.get_operand (r&: true_range, expr: name);
998	if (!compute_operand_range (r&: false_range, stmt: src_stmt, lhs: m_bool_zero, name, src))
999	src.get_operand (r&: false_range, expr: name);
1000	}
1001
1002
1003	// This routine will try to refine the ranges of OP1 and OP2 given a relation
1004	// K between them. In order to perform this refinement, one of the operands
1005	// must be in the definition chain of the other. The use is refined using
1006	// op1/op2_range on the statement, and the definition is then recalculated
1007	// using the relation.
1008
1009	bool
1010	gori_compute::refine_using_relation (tree op1, vrange &op1_range,
1011	tree op2, vrange &op2_range,
1012	fur_source &src, relation_kind k)
1013	{
1014	gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1015	gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1016
1017	if (k == VREL_VARYING || k == VREL_EQ || k == VREL_UNDEFINED)
1018	return false;
1019
1020	bool change = false;
1021	bool op1_def_p = in_chain_p (name: op2, def: op1);
1022	if (!op1_def_p)
1023	if (!in_chain_p (name: op1, def: op2))
1024	return false;
1025
1026	tree def_op = op1_def_p ? op1 : op2;
1027	tree use_op = op1_def_p ? op2 : op1;
1028
1029	if (!op1_def_p)
1030	k = relation_swap (r: k);
1031
1032	// op1_def is true if we want to look up op1, otherwise we want op2.
1033	// if neither is the case, we returned in the above check.
1034
1035	gimple *def_stmt = SSA_NAME_DEF_STMT (def_op);
1036	gimple_range_op_handler op_handler (def_stmt);
1037	if (!op_handler)
1038	return false;
1039	tree def_op1 = op_handler.operand1 ();
1040	tree def_op2 = op_handler.operand2 ();
1041	// if the def isn't binary, the relation will not be useful.
1042	if (!def_op2)
1043	return false;
1044
1045	// Determine if op2 is directly referenced as an operand.
1046	if (def_op1 == use_op)
1047	{
1048	// def_stmt has op1 in the 1st operand position.
1049	Value_Range other_op (TREE_TYPE (def_op2));
1050	src.get_operand (r&: other_op, expr: def_op2);
1051
1052	// Using op1_range as the LHS, and relation REL, evaluate op2.
1053	tree type = TREE_TYPE (def_op1);
1054	Value_Range new_result (type);
1055	if (!op_handler.op1_range (r&: new_result, type,
1056	lhs: op1_def_p ? op1_range : op2_range,
1057	op2: other_op, relation_trio::lhs_op1 (k)))
1058	return false;
1059	if (op1_def_p)
1060	{
1061	change |= op2_range.intersect (new_result);
1062	// Recalculate op2.
1063	if (op_handler.fold_range (r&: new_result, type, lh: op2_range, rh: other_op))
1064	{
1065	change |= op1_range.intersect (new_result);
1066	}
1067	}
1068	else
1069	{
1070	change |= op1_range.intersect (new_result);
1071	// Recalculate op1.
1072	if (op_handler.fold_range (r&: new_result, type, lh: op1_range, rh: other_op))
1073	{
1074	change |= op2_range.intersect (new_result);
1075	}
1076	}
1077	}
1078	else if (def_op2 == use_op)
1079	{
1080	// def_stmt has op1 in the 1st operand position.
1081	Value_Range other_op (TREE_TYPE (def_op1));
1082	src.get_operand (r&: other_op, expr: def_op1);
1083
1084	// Using op1_range as the LHS, and relation REL, evaluate op2.
1085	tree type = TREE_TYPE (def_op2);
1086	Value_Range new_result (type);
1087	if (!op_handler.op2_range (r&: new_result, type,
1088	lhs: op1_def_p ? op1_range : op2_range,
1089	op1: other_op, relation_trio::lhs_op2 (k)))
1090	return false;
1091	if (op1_def_p)
1092	{
1093	change |= op2_range.intersect (new_result);
1094	// Recalculate op1.
1095	if (op_handler.fold_range (r&: new_result, type, lh: other_op, rh: op2_range))
1096	{
1097	change |= op1_range.intersect (new_result);
1098	}
1099	}
1100	else
1101	{
1102	change |= op1_range.intersect (new_result);
1103	// Recalculate op2.
1104	if (op_handler.fold_range (r&: new_result, type, lh: other_op, rh: op1_range))
1105	{
1106	change |= op2_range.intersect (new_result);
1107	}
1108	}
1109	}
1110	return change;
1111	}
1112
1113	// Calculate a range for NAME from the operand 1 position of STMT
1114	// assuming the result of the statement is LHS. Return the range in
1115	// R, or false if no range could be calculated.
1116
1117	bool
1118	gori_compute::compute_operand1_range (vrange &r,
1119	gimple_range_op_handler &handler,
1120	const vrange &lhs,
1121	fur_source &src, value_relation *rel)
1122	{
1123	gimple *stmt = handler.stmt ();
1124	tree op1 = handler.operand1 ();
1125	tree op2 = handler.operand2 ();
1126	tree lhs_name = gimple_get_lhs (stmt);
1127
1128	relation_trio trio;
1129	if (rel)
1130	trio = rel->create_trio (lhs: lhs_name, op1, op2);
1131
1132	Value_Range op1_range (TREE_TYPE (op1));
1133	Value_Range op2_range (op2 ? TREE_TYPE (op2) : TREE_TYPE (op1));
1134
1135	// Fetch the known range for op1 in this block.
1136	src.get_operand (r&: op1_range, expr: op1);
1137
1138	// Now range-op calculate and put that result in r.
1139	if (op2)
1140	{
1141	src.get_operand (r&: op2_range, expr: op2);
1142
1143	relation_kind op_op = trio.op1_op2 ();
1144	if (op_op != VREL_VARYING)
1145	refine_using_relation (op1, op1_range, op2, op2_range, src, k: op_op);
1146
1147	// If op1 == op2, create a new trio for just this call.
1148	if (op1 == op2 && gimple_range_ssa_p (exp: op1))
1149	trio = relation_trio (trio.lhs_op1 (), trio.lhs_op2 (), VREL_EQ);
1150	if (!handler.calc_op1 (r, lhs_range: lhs, op2_range, trio))
1151	return false;
1152	}
1153	else
1154	{
1155	// We pass op1_range to the unary operation. Normally it's a
1156	// hidden range_for_type parameter, but sometimes having the
1157	// actual range can result in better information.
1158	if (!handler.calc_op1 (r, lhs_range: lhs, op2_range: op1_range, trio))
1159	return false;
1160	}
1161
1162	unsigned idx;
1163	if ((idx = tracer.header (str: "compute op 1 (")))
1164	{
1165	print_generic_expr (dump_file, op1, TDF_SLIM);
1166	fprintf (stream: dump_file, format: ") at ");
1167	print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1168	tracer.print (counter: idx, str: "LHS =");
1169	lhs.dump (dump_file);
1170	if (op2 && TREE_CODE (op2) == SSA_NAME)
1171	{
1172	fprintf (stream: dump_file, format: ", ");
1173	print_generic_expr (dump_file, op2, TDF_SLIM);
1174	fprintf (stream: dump_file, format: " = ");
1175	op2_range.dump (dump_file);
1176	}
1177	fprintf (stream: dump_file, format: "\n");
1178	tracer.print (counter: idx, str: "Computes ");
1179	print_generic_expr (dump_file, op1, TDF_SLIM);
1180	fprintf (stream: dump_file, format: " = ");
1181	r.dump (dump_file);
1182	fprintf (stream: dump_file, format: " intersect Known range : ");
1183	op1_range.dump (dump_file);
1184	fputc (c: '\n', stream: dump_file);
1185	}
1186
1187	r.intersect (op1_range);
1188	if (idx)
1189	tracer.trailer (counter: idx, caller: "produces ", result: true, name: op1, r);
1190	return true;
1191	}
1192
1193
1194	// Calculate a range for NAME from the operand 2 position of S
1195	// assuming the result of the statement is LHS. Return the range in
1196	// R, or false if no range could be calculated.
1197
1198	bool
1199	gori_compute::compute_operand2_range (vrange &r,
1200	gimple_range_op_handler &handler,
1201	const vrange &lhs,
1202	fur_source &src, value_relation *rel)
1203	{
1204	gimple *stmt = handler.stmt ();
1205	tree op1 = handler.operand1 ();
1206	tree op2 = handler.operand2 ();
1207	tree lhs_name = gimple_get_lhs (stmt);
1208
1209	Value_Range op1_range (TREE_TYPE (op1));
1210	Value_Range op2_range (TREE_TYPE (op2));
1211
1212	src.get_operand (r&: op1_range, expr: op1);
1213	src.get_operand (r&: op2_range, expr: op2);
1214
1215	relation_trio trio;
1216	if (rel)
1217	trio = rel->create_trio (lhs: lhs_name, op1, op2);
1218	relation_kind op_op = trio.op1_op2 ();
1219
1220	if (op_op != VREL_VARYING)
1221	refine_using_relation (op1, op1_range, op2, op2_range, src, k: op_op);
1222
1223	// If op1 == op2, create a new trio for this stmt.
1224	if (op1 == op2 && gimple_range_ssa_p (exp: op1))
1225	trio = relation_trio (trio.lhs_op1 (), trio.lhs_op2 (), VREL_EQ);
1226	// Intersect with range for op2 based on lhs and op1.
1227	if (!handler.calc_op2 (r, lhs_range: lhs, op1_range, trio))
1228	return false;
1229
1230	unsigned idx;
1231	if ((idx = tracer.header (str: "compute op 2 (")))
1232	{
1233	print_generic_expr (dump_file, op2, TDF_SLIM);
1234	fprintf (stream: dump_file, format: ") at ");
1235	print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1236	tracer.print (counter: idx, str: "LHS = ");
1237	lhs.dump (dump_file);
1238	if (TREE_CODE (op1) == SSA_NAME)
1239	{
1240	fprintf (stream: dump_file, format: ", ");
1241	print_generic_expr (dump_file, op1, TDF_SLIM);
1242	fprintf (stream: dump_file, format: " = ");
1243	op1_range.dump (dump_file);
1244	}
1245	fprintf (stream: dump_file, format: "\n");
1246	tracer.print (counter: idx, str: "Computes ");
1247	print_generic_expr (dump_file, op2, TDF_SLIM);
1248	fprintf (stream: dump_file, format: " = ");
1249	r.dump (dump_file);
1250	fprintf (stream: dump_file, format: " intersect Known range : ");
1251	op2_range.dump (dump_file);
1252	fputc (c: '\n', stream: dump_file);
1253	}
1254	// Intersect the calculated result with the known result and return if done.
1255	r.intersect (op2_range);
1256	if (idx)
1257	tracer.trailer (counter: idx, caller: " produces ", result: true, name: op2, r);
1258	return true;
1259	}
1260
1261	// Calculate a range for NAME from both operand positions of S
1262	// assuming the result of the statement is LHS. Return the range in
1263	// R, or false if no range could be calculated.
1264
1265	bool
1266	gori_compute::compute_operand1_and_operand2_range (vrange &r,
1267	gimple_range_op_handler
1268	&handler,
1269	const vrange &lhs,
1270	tree name,
1271	fur_source &src,
1272	value_relation *rel)
1273	{
1274	Value_Range op_range (TREE_TYPE (name));
1275
1276	Value_Range vr (TREE_TYPE (handler.operand2 ()));
1277	// Calculate a good a range through op2.
1278	if (!compute_operand2_range (r&: vr, handler, lhs, src, rel))
1279	return false;
1280	gimple *src_stmt = SSA_NAME_DEF_STMT (handler.operand2 ());
1281	gcc_checking_assert (src_stmt);
1282	// Then feed this range back as the LHS of the defining statement.
1283	if (!compute_operand_range (r, stmt: src_stmt, lhs: vr, name, src, rel))
1284	return false;
1285
1286	// Now get the range thru op1.
1287	vr.set_type (TREE_TYPE (handler.operand1 ()));
1288	if (!compute_operand1_range (r&: vr, handler, lhs, src, rel))
1289	return false;
1290	src_stmt = SSA_NAME_DEF_STMT (handler.operand1 ());
1291	gcc_checking_assert (src_stmt);
1292	// Then feed this range back as the LHS of the defining statement.
1293	if (!compute_operand_range (r&: op_range, stmt: src_stmt, lhs: vr, name, src, rel))
1294	return false;
1295
1296	// Both operands have to be simultaneously true, so perform an intersection.
1297	r.intersect (op_range);
1298	return true;
1299	}
1300
1301	// Return TRUE if NAME can be recomputed on any edge exiting BB. If any
1302	// direct dependent is exported, it may also change the computed value of NAME.
1303
1304	bool
1305	gori_compute::may_recompute_p (tree name, basic_block bb, int depth)
1306	{
1307	tree dep1 = depend1 (name);
1308	tree dep2 = depend2 (name);
1309
1310	// If the first dependency is not set, there is no recomputation.
1311	// Dependencies reflect original IL, not current state. Check if the
1312	// SSA_NAME is still valid as well.
1313	if (!dep1)
1314	return false;
1315
1316	// Don't recalculate PHIs or statements with side_effects.
1317	gimple *s = SSA_NAME_DEF_STMT (name);
1318	if (is_a<gphi *> (p: s) || gimple_has_side_effects (s))
1319	return false;
1320
1321	if (!dep2)
1322	{
1323	// -1 indicates a default param, convert it to the real default.
1324	if (depth == -1)
1325	{
1326	depth = (int)param_ranger_recompute_depth;
1327	gcc_checking_assert (depth >= 1);
1328	}
1329
1330	bool res = (bb ? is_export_p (name: dep1, bb) : is_export_p (name: dep1));
1331	if (res || depth <= 1)
1332	return res;
1333	// Check another level of recomputation.
1334	return may_recompute_p (name: dep1, bb, depth: --depth);
1335	}
1336	// Two dependencies terminate the depth of the search.
1337	if (bb)
1338	return is_export_p (name: dep1, bb) || is_export_p (name: dep2, bb);
1339	else
1340	return is_export_p (name: dep1) || is_export_p (name: dep2);
1341	}
1342
1343	// Return TRUE if NAME can be recomputed on edge E. If any direct dependent
1344	// is exported on edge E, it may change the computed value of NAME.
1345
1346	bool
1347	gori_compute::may_recompute_p (tree name, edge e, int depth)
1348	{
1349	gcc_checking_assert (e);
1350	return may_recompute_p (name, bb: e->src, depth);
1351	}
1352
1353
1354	// Return TRUE if a range can be calculated or recomputed for NAME on any
1355	// edge exiting BB.
1356
1357	bool
1358	gori_compute::has_edge_range_p (tree name, basic_block bb)
1359	{
1360	// Check if NAME is an export or can be recomputed.
1361	if (bb)
1362	return is_export_p (name, bb) || may_recompute_p (name, bb);
1363
1364	// If no block is specified, check for anywhere in the IL.
1365	return is_export_p (name) || may_recompute_p (name);
1366	}
1367
1368	// Return TRUE if a range can be calculated or recomputed for NAME on edge E.
1369
1370	bool
1371	gori_compute::has_edge_range_p (tree name, edge e)
1372	{
1373	gcc_checking_assert (e);
1374	return has_edge_range_p (name, bb: e->src);
1375	}
1376
1377	// Calculate a range on edge E and return it in R. Try to evaluate a
1378	// range for NAME on this edge. Return FALSE if this is either not a
1379	// control edge or NAME is not defined by this edge.
1380
1381	bool
1382	gori_compute::outgoing_edge_range_p (vrange &r, edge e, tree name,
1383	range_query &q)
1384	{
1385	unsigned idx;
1386
1387	if ((e->flags & m_not_executable_flag))
1388	{
1389	r.set_undefined ();
1390	if (dump_file && (dump_flags & TDF_DETAILS))
1391	fprintf (stream: dump_file, format: "Outgoing edge %d->%d unexecutable.\n",
1392	e->src->index, e->dest->index);
1393	return true;
1394	}
1395
1396	gcc_checking_assert (gimple_range_ssa_p (name));
1397	int_range_max lhs;
1398	// Determine if there is an outgoing edge.
1399	gimple *stmt = outgoing.edge_range_p (r&: lhs, e);
1400	if (!stmt)
1401	return false;
1402
1403	fur_stmt src (stmt, &q);
1404	// If NAME can be calculated on the edge, use that.
1405	if (is_export_p (name, bb: e->src))
1406	{
1407	bool res;
1408	if ((idx = tracer.header (str: "outgoing_edge")))
1409	{
1410	fprintf (stream: dump_file, format: " for ");
1411	print_generic_expr (dump_file, name, TDF_SLIM);
1412	fprintf (stream: dump_file, format: " on edge %d->%d\n",
1413	e->src->index, e->dest->index);
1414	}
1415	if ((res = compute_operand_range (r, stmt, lhs, name, src)))
1416	{
1417	// Sometimes compatible types get interchanged. See PR97360.
1418	// Make sure we are returning the type of the thing we asked for.
1419	if (!r.undefined_p () && r.type () != TREE_TYPE (name))
1420	{
1421	gcc_checking_assert (range_compatible_p (r.type (),
1422	TREE_TYPE (name)));
1423	range_cast (r, TREE_TYPE (name));
1424	}
1425	}
1426	if (idx)
1427	tracer.trailer (counter: idx, caller: "outgoing_edge", result: res, name, r);
1428	return res;
1429	}
1430	// If NAME isn't exported, check if it can be recomputed.
1431	else if (may_recompute_p (name, e))
1432	{
1433	gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1434
1435	if ((idx = tracer.header (str: "recomputation")))
1436	{
1437	fprintf (stream: dump_file, format: " attempt on edge %d->%d for ",
1438	e->src->index, e->dest->index);
1439	print_gimple_stmt (dump_file, def_stmt, 0, TDF_SLIM);
1440	}
1441	// Simply calculate DEF_STMT on edge E using the range query Q.
1442	fold_range (v&: r, s: def_stmt, on_edge: e, q: &q);
1443	if (idx)
1444	tracer.trailer (counter: idx, caller: "recomputation", result: true, name, r);
1445	return true;
1446	}
1447	return false;
1448	}
1449
1450	// Given COND ? OP1 : OP2 with ranges R1 for OP1 and R2 for OP2, Use gori
1451	// to further resolve R1 and R2 if there are any dependencies between
1452	// OP1 and COND or OP2 and COND. All values can are to be calculated using SRC
1453	// as the origination source location for operands..
1454	// Effectively, use COND an the edge condition and solve for OP1 on the true
1455	// edge and OP2 on the false edge.
1456
1457	bool
1458	gori_compute::condexpr_adjust (vrange &r1, vrange &r2, gimple *, tree cond,
1459	tree op1, tree op2, fur_source &src)
1460	{
1461	tree ssa1 = gimple_range_ssa_p (exp: op1);
1462	tree ssa2 = gimple_range_ssa_p (exp: op2);
1463	if (!ssa1 && !ssa2)
1464	return false;
1465	if (TREE_CODE (cond) != SSA_NAME)
1466	return false;
1467	gassign *cond_def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (cond));
1468	if (!cond_def
1469	|| TREE_CODE_CLASS (gimple_assign_rhs_code (cond_def)) != tcc_comparison)
1470	return false;
1471	tree type = TREE_TYPE (gimple_assign_rhs1 (cond_def));
1472	if (!range_compatible_p (type1: type, TREE_TYPE (gimple_assign_rhs2 (cond_def))))
1473	return false;
1474	range_op_handler hand (gimple_assign_rhs_code (gs: cond_def));
1475	if (!hand)
1476	return false;
1477
1478	tree c1 = gimple_range_ssa_p (exp: gimple_assign_rhs1 (gs: cond_def));
1479	tree c2 = gimple_range_ssa_p (exp: gimple_assign_rhs2 (gs: cond_def));
1480
1481	// Only solve if there is one SSA name in the condition.
1482	if ((!c1 && !c2) || (c1 && c2))
1483	return false;
1484
1485	// Pick up the current values of each part of the condition.
1486	tree rhs1 = gimple_assign_rhs1 (gs: cond_def);
1487	tree rhs2 = gimple_assign_rhs2 (gs: cond_def);
1488	Value_Range cl (TREE_TYPE (rhs1));
1489	Value_Range cr (TREE_TYPE (rhs2));
1490	src.get_operand (r&: cl, expr: rhs1);
1491	src.get_operand (r&: cr, expr: rhs2);
1492
1493	tree cond_name = c1 ? c1 : c2;
1494	gimple *def_stmt = SSA_NAME_DEF_STMT (cond_name);
1495
1496	// Evaluate the value of COND_NAME on the true and false edges, using either
1497	// the op1 or op2 routines based on its location.
1498	Value_Range cond_true (type), cond_false (type);
1499	if (c1)
1500	{
1501	if (!hand.op1_range (r&: cond_false, type, lhs: m_bool_zero, op2: cr))
1502	return false;
1503	if (!hand.op1_range (r&: cond_true, type, lhs: m_bool_one, op2: cr))
1504	return false;
1505	cond_false.intersect (r: cl);
1506	cond_true.intersect (r: cl);
1507	}
1508	else
1509	{
1510	if (!hand.op2_range (r&: cond_false, type, lhs: m_bool_zero, op1: cl))
1511	return false;
1512	if (!hand.op2_range (r&: cond_true, type, lhs: m_bool_one, op1: cl))
1513	return false;
1514	cond_false.intersect (r: cr);
1515	cond_true.intersect (r: cr);
1516	}
1517
1518	unsigned idx;
1519	if ((idx = tracer.header (str: "cond_expr evaluation : ")))
1520	{
1521	fprintf (stream: dump_file, format: " range1 = ");
1522	r1.dump (dump_file);
1523	fprintf (stream: dump_file, format: ", range2 = ");
1524	r1.dump (dump_file);
1525	fprintf (stream: dump_file, format: "\n");
1526	}
1527
1528	// Now solve for SSA1 or SSA2 if they are in the dependency chain.
1529	if (ssa1 && in_chain_p (name: ssa1, def: cond_name))
1530	{
1531	Value_Range tmp1 (TREE_TYPE (ssa1));
1532	if (compute_operand_range (r&: tmp1, stmt: def_stmt, lhs: cond_true, name: ssa1, src))
1533	r1.intersect (tmp1);
1534	}
1535	if (ssa2 && in_chain_p (name: ssa2, def: cond_name))
1536	{
1537	Value_Range tmp2 (TREE_TYPE (ssa2));
1538	if (compute_operand_range (r&: tmp2, stmt: def_stmt, lhs: cond_false, name: ssa2, src))
1539	r2.intersect (tmp2);
1540	}
1541	if (idx)
1542	{
1543	tracer.print (counter: idx, str: "outgoing: range1 = ");
1544	r1.dump (dump_file);
1545	fprintf (stream: dump_file, format: ", range2 = ");
1546	r1.dump (dump_file);
1547	fprintf (stream: dump_file, format: "\n");
1548	tracer.trailer (counter: idx, caller: "cond_expr", result: true, name: cond_name, r: cond_true);
1549	}
1550	return true;
1551	}
1552
1553	// Dump what is known to GORI computes to listing file F.
1554
1555	void
1556	gori_compute::dump (FILE *f)
1557	{
1558	gori_map::dump (f);
1559	}
1560
1561	// ------------------------------------------------------------------------
1562	// GORI iterator. Although we have bitmap iterators, don't expose that it
1563	// is currently a bitmap. Use an export iterator to hide future changes.
1564
1565	// Construct a basic iterator over an export bitmap.
1566
1567	gori_export_iterator::gori_export_iterator (bitmap b)
1568	{
1569	bm = b;
1570	if (b)
1571	bmp_iter_set_init (bi: &bi, map: b, start_bit: 1, bit_no: &y);
1572	}
1573
1574
1575	// Move to the next export bitmap spot.
1576
1577	void
1578	gori_export_iterator::next ()
1579	{
1580	bmp_iter_next (bi: &bi, bit_no: &y);
1581	}
1582
1583
1584	// Fetch the name of the next export in the export list. Return NULL if
1585	// iteration is done.
1586
1587	tree
1588	gori_export_iterator::get_name ()
1589	{
1590	if (!bm)
1591	return NULL_TREE;
1592
1593	while (bmp_iter_set (bi: &bi, bit_no: &y))
1594	{
1595	tree t = ssa_name (y);
1596	if (t)
1597	return t;
1598	next ();
1599	}
1600	return NULL_TREE;
1601	}
1602
1603	// This is a helper class to set up STMT with a known LHS for further GORI
1604	// processing.
1605
1606	class gori_stmt_info : public gimple_range_op_handler
1607	{
1608	public:
1609	gori_stmt_info (vrange &lhs, gimple *stmt, range_query *q);
1610	Value_Range op1_range;
1611	Value_Range op2_range;
1612	tree ssa1;
1613	tree ssa2;
1614	};
1615
1616
1617	// Uses query Q to get the known ranges on STMT with a LHS range
1618	// for op1_range and op2_range and set ssa1 and ssa2 if either or both of
1619	// those operands are SSA_NAMES.
1620
1621	gori_stmt_info::gori_stmt_info (vrange &lhs, gimple *stmt, range_query *q)
1622	: gimple_range_op_handler (stmt)
1623	{
1624	ssa1 = NULL;
1625	ssa2 = NULL;
1626	// Don't handle switches as yet for vector processing.
1627	if (is_a<gswitch *> (p: stmt))
1628	return;
1629
1630	// No frther processing for VARYING or undefined.
1631	if (lhs.undefined_p () || lhs.varying_p ())
1632	return;
1633
1634	// If there is no range-op handler, we are also done.
1635	if (!*this)
1636	return;
1637
1638	// Only evaluate logical cases if both operands must be the same as the LHS.
1639	// Otherwise its becomes exponential in time, as well as more complicated.
1640	if (is_gimple_logical_p (gs: stmt))
1641	{
1642	gcc_checking_assert (range_compatible_p (lhs.type (), boolean_type_node));
1643	enum tree_code code = gimple_expr_code (stmt);
1644	if (code == TRUTH_OR_EXPR || code == BIT_IOR_EXPR)
1645	{
1646	// [0, 0] = x || y means both x and y must be zero.
1647	if (!lhs.singleton_p () || !lhs.zero_p ())
1648	return;
1649	}
1650	else if (code == TRUTH_AND_EXPR || code == BIT_AND_EXPR)
1651	{
1652	// [1, 1] = x && y means both x and y must be one.
1653	if (!lhs.singleton_p () || lhs.zero_p ())
1654	return;
1655	}
1656	}
1657
1658	tree op1 = operand1 ();
1659	tree op2 = operand2 ();
1660	ssa1 = gimple_range_ssa_p (exp: op1);
1661	ssa2 = gimple_range_ssa_p (exp: op2);
1662	// If both operands are the same, only process one of them.
1663	if (ssa1 && ssa1 == ssa2)
1664	ssa2 = NULL_TREE;
1665
1666	// Extract current ranges for the operands.
1667	fur_stmt src (stmt, q);
1668	if (op1)
1669	{
1670	op1_range.set_type (TREE_TYPE (op1));
1671	src.get_operand (r&: op1_range, expr: op1);
1672	}
1673
1674	// And satisfy the second operand for single op satements.
1675	if (op2)
1676	{
1677	op2_range.set_type (TREE_TYPE (op2));
1678	src.get_operand (r&: op2_range, expr: op2);
1679	}
1680	else if (op1)
1681	op2_range = op1_range;
1682	return;
1683	}
1684
1685
1686	// Process STMT using LHS as the range of the LHS. Invoke GORI processing
1687	// to resolve ranges for all SSA_NAMES feeding STMT which may be altered
1688	// based on LHS. Fill R with the results, and resolve all incoming
1689	// ranges using range-query Q.
1690
1691	static void
1692	gori_calc_operands (vrange &lhs, gimple *stmt, ssa_cache &r, range_query *q)
1693	{
1694	struct gori_stmt_info si(lhs, stmt, q);
1695	if (!si)
1696	return;
1697
1698	Value_Range tmp;
1699	// Now evaluate operand ranges, and set them in the edge cache.
1700	// If there was already a range, leave it and do no further evaluation.
1701	if (si.ssa1 && !r.has_range (name: si.ssa1))
1702	{
1703	tmp.set_type (TREE_TYPE (si.ssa1));
1704	if (si.calc_op1 (r&: tmp, lhs_range: lhs, op2_range: si.op2_range))
1705	si.op1_range.intersect (r: tmp);
1706	r.set_range (name: si.ssa1, r: si.op1_range);
1707	gimple *src = SSA_NAME_DEF_STMT (si.ssa1);
1708	// If defintion is in the same basic lock, evaluate it.
1709	if (src && gimple_bb (g: src) == gimple_bb (g: stmt))
1710	gori_calc_operands (lhs&: si.op1_range, stmt: src, r, q);
1711	}
1712
1713	if (si.ssa2 && !r.has_range (name: si.ssa2))
1714	{
1715	tmp.set_type (TREE_TYPE (si.ssa2));
1716	if (si.calc_op2 (r&: tmp, lhs_range: lhs, op1_range: si.op1_range))
1717	si.op2_range.intersect (r: tmp);
1718	r.set_range (name: si.ssa2, r: si.op2_range);
1719	gimple *src = SSA_NAME_DEF_STMT (si.ssa2);
1720	if (src && gimple_bb (g: src) == gimple_bb (g: stmt))
1721	gori_calc_operands (lhs&: si.op2_range, stmt: src, r, q);
1722	}
1723	}
1724
1725	// Use ssa_cache R as a repository for all outgoing ranges on edge E that
1726	// can be calculated. Use OGR if present to establish starting edge ranges,
1727	// and Q to resolve operand values. If Q is NULL use the current range
1728	// query available to the system.
1729
1730	bool
1731	gori_on_edge (ssa_cache &r, edge e, range_query *q, gimple_outgoing_range *ogr)
1732	{
1733	// Start with an empty vector
1734	r.clear ();
1735	int_range_max lhs;
1736	// Determine if there is an outgoing edge.
1737	gimple *stmt;
1738	if (ogr)
1739	stmt = ogr->edge_range_p (r&: lhs, e);
1740	else
1741	{
1742	stmt = gimple_outgoing_range_stmt_p (bb: e->src);
1743	if (stmt && is_a<gcond *> (p: stmt))
1744	gcond_edge_range (r&: lhs, e);
1745	else
1746	stmt = NULL;
1747	}
1748	if (!stmt)
1749	return false;
1750	gori_calc_operands (lhs, stmt, r, q);
1751	return true;
1752	}
1753
1754	// Helper for GORI_NAME_ON_EDGE which uses query Q to determine if STMT
1755	// provides a range for NAME, and returns it in R if so. If it does not,
1756	// continue processing feeding statments until we run out of statements
1757	// or fine a range for NAME.
1758
1759	bool
1760	gori_name_helper (vrange &r, tree name, vrange &lhs, gimple *stmt,
1761	range_query *q)
1762	{
1763	struct gori_stmt_info si(lhs, stmt, q);
1764	if (!si)
1765	return false;
1766
1767	if (si.ssa1 == name)
1768	return si.calc_op1 (r, lhs_range: lhs, op2_range: si.op2_range);
1769	if (si.ssa2 == name)
1770	return si.calc_op2 (r, lhs_range: lhs, op1_range: si.op1_range);
1771
1772	Value_Range tmp;
1773	// Now evaluate operand ranges, and set them in the edge cache.
1774	// If there was already a range, leave it and do no further evaluation.
1775	if (si.ssa1)
1776	{
1777	tmp.set_type (TREE_TYPE (si.ssa1));
1778	if (si.calc_op1 (r&: tmp, lhs_range: lhs, op2_range: si.op2_range))
1779	si.op1_range.intersect (r: tmp);
1780	gimple *src = SSA_NAME_DEF_STMT (si.ssa1);
1781	// If defintion is in the same basic lock, evaluate it.
1782	if (src && gimple_bb (g: src) == gimple_bb (g: stmt))
1783	if (gori_name_helper (r, name, lhs&: si.op1_range, stmt: src, q))
1784	return true;
1785	}
1786
1787	if (si.ssa2)
1788	{
1789	tmp.set_type (TREE_TYPE (si.ssa2));
1790	if (si.calc_op2 (r&: tmp, lhs_range: lhs, op1_range: si.op1_range))
1791	si.op2_range.intersect (r: tmp);
1792	gimple *src = SSA_NAME_DEF_STMT (si.ssa2);
1793	if (src && gimple_bb (g: src) == gimple_bb (g: stmt))
1794	if (gori_name_helper (r, name, lhs&: si.op2_range, stmt: src, q))
1795	return true;
1796	}
1797	return false;
1798	}
1799
1800	// Check if NAME has an outgoing range on edge E. Use query Q to evaluate
1801	// the operands. Return TRUE and the range in R if there is an outgoing range.
1802	// This is like gori_on_edge except it only looks for the single name and
1803	// does not require an ssa_cache.
1804
1805	bool
1806	gori_name_on_edge (vrange &r, tree name, edge e, range_query *q)
1807	{
1808	int_range_max lhs;
1809	gimple *stmt = gimple_outgoing_range_stmt_p (bb: e->src);
1810	if (!stmt || !is_a<gcond *> (p: stmt))
1811	return false;
1812	gcond_edge_range (r&: lhs, e);
1813	return gori_name_helper (r, name, lhs, stmt, q);
1814	}
1815