1	/* Header file for the value range relational processing.
2	Copyright (C) 2020-2023 Free Software Foundation, Inc.
3	Contributed by Andrew MacLeod <amacleod@redhat.com>
4
5	This file is part of GCC.
6
7	GCC is free software; you can redistribute it and/or modify it under
8	the terms of the GNU General Public License as published by the Free
9	Software Foundation; either version 3, or (at your option) any later
10	version.
11
12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15	for more details.
16
17	You should have received a copy of the GNU General Public License
18	along with GCC; see the file COPYING3. If not see
19	<http://www.gnu.org/licenses/>. */
20
21	#include "config.h"
22	#include "system.h"
23	#include "coretypes.h"
24	#include "backend.h"
25	#include "tree.h"
26	#include "gimple.h"
27	#include "ssa.h"
28
29	#include "gimple-range.h"
30	#include "tree-pretty-print.h"
31	#include "gimple-pretty-print.h"
32	#include "alloc-pool.h"
33	#include "dominance.h"
34
35	static const char *const kind_string[VREL_LAST] =
36	{ "varying", "undefined", "<", "<=", ">", ">=", "==", "!=", "pe8", "pe16",
37	"pe32", "pe64" };
38
39	// Print a relation_kind REL to file F.
40
41	void
42	print_relation (FILE *f, relation_kind rel)
43	{
44	fprintf (stream: f, format: " %s ", kind_string[rel]);
45	}
46
47	// This table is used to negate the operands. op1 REL op2 -> !(op1 REL op2).
48	static const unsigned char rr_negate_table[VREL_LAST] = {
49	VREL_VARYING, VREL_UNDEFINED, VREL_GE, VREL_GT, VREL_LE, VREL_LT, VREL_NE,
50	VREL_EQ };
51
52	// Negate the relation, as in logical negation.
53
54	relation_kind
55	relation_negate (relation_kind r)
56	{
57	return relation_kind (rr_negate_table [r]);
58	}
59
60	// This table is used to swap the operands. op1 REL op2 -> op2 REL op1.
61	static const unsigned char rr_swap_table[VREL_LAST] = {
62	VREL_VARYING, VREL_UNDEFINED, VREL_GT, VREL_GE, VREL_LT, VREL_LE, VREL_EQ,
63	VREL_NE };
64
65	// Return the relation as if the operands were swapped.
66
67	relation_kind
68	relation_swap (relation_kind r)
69	{
70	return relation_kind (rr_swap_table [r]);
71	}
72
73	// This table is used to perform an intersection between 2 relations.
74
75	static const unsigned char rr_intersect_table[VREL_LAST][VREL_LAST] = {
76	// VREL_VARYING
77	{ VREL_VARYING, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ,
78	VREL_NE },
79	// VREL_UNDEFINED
80	{ VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED,
81	VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED },
82	// VREL_LT
83	{ VREL_LT, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_UNDEFINED, VREL_UNDEFINED,
84	VREL_UNDEFINED, VREL_LT },
85	// VREL_LE
86	{ VREL_LE, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_UNDEFINED, VREL_EQ,
87	VREL_EQ, VREL_LT },
88	// VREL_GT
89	{ VREL_GT, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_GT, VREL_GT,
90	VREL_UNDEFINED, VREL_GT },
91	// VREL_GE
92	{ VREL_GE, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_GT, VREL_GE,
93	VREL_EQ, VREL_GT },
94	// VREL_EQ
95	{ VREL_EQ, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_UNDEFINED, VREL_EQ,
96	VREL_EQ, VREL_UNDEFINED },
97	// VREL_NE
98	{ VREL_NE, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_GT, VREL_GT,
99	VREL_UNDEFINED, VREL_NE } };
100
101
102	// Intersect relation R1 with relation R2 and return the resulting relation.
103
104	relation_kind
105	relation_intersect (relation_kind r1, relation_kind r2)
106	{
107	return relation_kind (rr_intersect_table[r1][r2]);
108	}
109
110
111	// This table is used to perform a union between 2 relations.
112
113	static const unsigned char rr_union_table[VREL_LAST][VREL_LAST] = {
114	// VREL_VARYING
115	{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
116	VREL_VARYING, VREL_VARYING, VREL_VARYING },
117	// VREL_UNDEFINED
118	{ VREL_VARYING, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_GT, VREL_GE,
119	VREL_EQ, VREL_NE },
120	// VREL_LT
121	{ VREL_VARYING, VREL_LT, VREL_LT, VREL_LE, VREL_NE, VREL_VARYING, VREL_LE,
122	VREL_NE },
123	// VREL_LE
124	{ VREL_VARYING, VREL_LE, VREL_LE, VREL_LE, VREL_VARYING, VREL_VARYING,
125	VREL_LE, VREL_VARYING },
126	// VREL_GT
127	{ VREL_VARYING, VREL_GT, VREL_NE, VREL_VARYING, VREL_GT, VREL_GE, VREL_GE,
128	VREL_NE },
129	// VREL_GE
130	{ VREL_VARYING, VREL_GE, VREL_VARYING, VREL_VARYING, VREL_GE, VREL_GE,
131	VREL_GE, VREL_VARYING },
132	// VREL_EQ
133	{ VREL_VARYING, VREL_EQ, VREL_LE, VREL_LE, VREL_GE, VREL_GE, VREL_EQ,
134	VREL_VARYING },
135	// VREL_NE
136	{ VREL_VARYING, VREL_NE, VREL_NE, VREL_VARYING, VREL_NE, VREL_VARYING,
137	VREL_VARYING, VREL_NE } };
138
139	// Union relation R1 with relation R2 and return the result.
140
141	relation_kind
142	relation_union (relation_kind r1, relation_kind r2)
143	{
144	return relation_kind (rr_union_table[r1][r2]);
145	}
146
147
148	// This table is used to determine transitivity between 2 relations.
149	// (A relation0 B) and (B relation1 C) implies (A result C)
150
151	static const unsigned char rr_transitive_table[VREL_LAST][VREL_LAST] = {
152	// VREL_VARYING
153	{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
154	VREL_VARYING, VREL_VARYING, VREL_VARYING },
155	// VREL_UNDEFINED
156	{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
157	VREL_VARYING, VREL_VARYING, VREL_VARYING },
158	// VREL_LT
159	{ VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LT, VREL_VARYING, VREL_VARYING,
160	VREL_LT, VREL_VARYING },
161	// VREL_LE
162	{ VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_VARYING, VREL_VARYING,
163	VREL_LE, VREL_VARYING },
164	// VREL_GT
165	{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GT,
166	VREL_GT, VREL_VARYING },
167	// VREL_GE
168	{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GE,
169	VREL_GE, VREL_VARYING },
170	// VREL_EQ
171	{ VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ,
172	VREL_VARYING },
173	// VREL_NE
174	{ VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
175	VREL_VARYING, VREL_VARYING, VREL_VARYING } };
176
177	// Apply transitive operation between relation R1 and relation R2, and
178	// return the resulting relation, if any.
179
180	relation_kind
181	relation_transitive (relation_kind r1, relation_kind r2)
182	{
183	return relation_kind (rr_transitive_table[r1][r2]);
184	}
185
186	// When one name is an equivalence of another, ensure the equivalence
187	// range is correct. Specifically for floating point, a +0 is also
188	// equivalent to a -0 which may not be reflected. See PR 111694.
189
190	void
191	adjust_equivalence_range (vrange &range)
192	{
193	if (range.undefined_p () || !is_a<frange> (v&: range))
194	return;
195
196	frange fr = as_a<frange> (v&: range);
197	// If range includes 0 make sure both signs of zero are included.
198	if (fr.contains_p (dconst0) || fr.contains_p (dconstm0))
199	{
200	frange zeros (range.type (), dconstm0, dconst0);
201	range.union_ (zeros);
202	}
203	}
204
205	// This vector maps a relation to the equivalent tree code.
206
207	static const tree_code relation_to_code [VREL_LAST] = {
208	ERROR_MARK, ERROR_MARK, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EQ_EXPR,
209	NE_EXPR };
210
211	// This routine validates that a relation can be applied to a specific set of
212	// ranges. In particular, floating point x == x may not be true if the NaN bit
213	// is set in the range. Symbolically the oracle will determine x == x,
214	// but specific range instances may override this.
215	// To verify, attempt to fold the relation using the supplied ranges.
216	// One would expect [1,1] to be returned, anything else means there is something
217	// in the range preventing the relation from applying.
218	// If there is no mechanism to verify, assume the relation is acceptable.
219
220	relation_kind
221	relation_oracle::validate_relation (relation_kind rel, vrange &op1, vrange &op2)
222	{
223	// If there is no mapping to a tree code, leave the relation as is.
224	tree_code code = relation_to_code [rel];
225	if (code == ERROR_MARK)
226	return rel;
227
228	// Undefined ranges cannot be checked either.
229	if (op1.undefined_p () || op2.undefined_p ())
230	return rel;
231
232	tree t1 = op1.type ();
233	tree t2 = op2.type ();
234
235	// If the range types are not compatible, no relation can exist.
236	if (!range_compatible_p (type1: t1, type2: t2))
237	return VREL_VARYING;
238
239	// If there is no handler, leave the relation as is.
240	range_op_handler handler (code);
241	if (!handler)
242	return rel;
243
244	// If the relation cannot be folded for any reason, leave as is.
245	Value_Range result (boolean_type_node);
246	if (!handler.fold_range (r&: result, boolean_type_node, lh: op1, rh: op2,
247	relation_trio::op1_op2 (k: rel)))
248	return rel;
249
250	// The expression op1 REL op2 using REL should fold to [1,1].
251	// Any other result means the relation is not verified to be true.
252	if (result.varying_p () || result.zero_p ())
253	return VREL_VARYING;
254
255	return rel;
256	}
257
258	// If no range is available, create a varying range for each SSA name and
259	// verify.
260
261	relation_kind
262	relation_oracle::validate_relation (relation_kind rel, tree ssa1, tree ssa2)
263	{
264	Value_Range op1, op2;
265	op1.set_varying (TREE_TYPE (ssa1));
266	op2.set_varying (TREE_TYPE (ssa2));
267
268	return validate_relation (rel, op1, op2);
269	}
270
271	// Given an equivalence set EQUIV, set all the bits in B that are still valid
272	// members of EQUIV in basic block BB.
273
274	void
275	relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
276	{
277	unsigned i;
278	bitmap_iterator bi;
279	EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
280	{
281	tree ssa = ssa_name (i);
282	if (ssa && !SSA_NAME_IN_FREE_LIST (ssa))
283	{
284	const_bitmap ssa_equiv = equiv_set (ssa, bb);
285	if (ssa_equiv == equivs)
286	bitmap_set_bit (b, i);
287	}
288	}
289	}
290
291	// -------------------------------------------------------------------------
292
293	// The very first element in the m_equiv chain is actually just a summary
294	// element in which the m_names bitmap is used to indicate that an ssa_name
295	// has an equivalence set in this block.
296	// This allows for much faster traversal of the DOM chain, as a search for
297	// SSA_NAME simply requires walking the DOM chain until a block is found
298	// which has the bit for SSA_NAME set. Then scan for the equivalency set in
299	// that block. No previous lists need be searched.
300
301	// If SSA has an equivalence in this list, find and return it.
302	// Otherwise return NULL.
303
304	equiv_chain *
305	equiv_chain::find (unsigned ssa)
306	{
307	equiv_chain *ptr = NULL;
308	// If there are equiv sets and SSA is in one in this list, find it.
309	// Otherwise return NULL.
310	if (bitmap_bit_p (m_names, ssa))
311	{
312	for (ptr = m_next; ptr; ptr = ptr->m_next)
313	if (bitmap_bit_p (ptr->m_names, ssa))
314	break;
315	}
316	return ptr;
317	}
318
319	// Dump the names in this equivalence set.
320
321	void
322	equiv_chain::dump (FILE *f) const
323	{
324	bitmap_iterator bi;
325	unsigned i;
326
327	if (!m_names || bitmap_empty_p (map: m_names))
328	return;
329	fprintf (stream: f, format: "Equivalence set : [");
330	unsigned c = 0;
331	EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
332	{
333	if (ssa_name (i))
334	{
335	if (c++)
336	fprintf (stream: f, format: ", ");
337	print_generic_expr (f, ssa_name (i), TDF_SLIM);
338	}
339	}
340	fprintf (stream: f, format: "]\n");
341	}
342
343	// Instantiate an equivalency oracle.
344
345	equiv_oracle::equiv_oracle ()
346	{
347	bitmap_obstack_initialize (&m_bitmaps);
348	m_equiv.create (nelems: 0);
349	m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
350	m_equiv_set = BITMAP_ALLOC (obstack: &m_bitmaps);
351	obstack_init (&m_chain_obstack);
352	m_self_equiv.create (nelems: 0);
353	m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
354	m_partial.create (nelems: 0);
355	m_partial.safe_grow_cleared (num_ssa_names + 1);
356	}
357
358	// Destruct an equivalency oracle.
359
360	equiv_oracle::~equiv_oracle ()
361	{
362	m_partial.release ();
363	m_self_equiv.release ();
364	obstack_free (&m_chain_obstack, NULL);
365	m_equiv.release ();
366	bitmap_obstack_release (&m_bitmaps);
367	}
368
369	// Add a partial equivalence R between OP1 and OP2.
370
371	void
372	equiv_oracle::add_partial_equiv (relation_kind r, tree op1, tree op2)
373	{
374	int v1 = SSA_NAME_VERSION (op1);
375	int v2 = SSA_NAME_VERSION (op2);
376	int prec2 = TYPE_PRECISION (TREE_TYPE (op2));
377	int bits = pe_to_bits (t: r);
378	gcc_checking_assert (bits && prec2 >= bits);
379
380	if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
381	m_partial.safe_grow_cleared (num_ssa_names + 1);
382	gcc_checking_assert (v1 < (int)m_partial.length ()
383	&& v2 < (int)m_partial.length ());
384
385	pe_slice &pe1 = m_partial[v1];
386	pe_slice &pe2 = m_partial[v2];
387
388	if (pe1.members)
389	{
390	// If the definition pe1 already has an entry, either the stmt is
391	// being re-evaluated, or the def was used before being registered.
392	// In either case, if PE2 has an entry, we simply do nothing.
393	if (pe2.members)
394	return;
395	// If there are no uses of op2, do not register.
396	if (has_zero_uses (var: op2))
397	return;
398	// PE1 is the LHS and already has members, so everything in the set
399	// should be a slice of PE2 rather than PE1.
400	pe2.code = pe_min (t1: r, t2: pe1.code);
401	pe2.ssa_base = op2;
402	pe2.members = pe1.members;
403	bitmap_iterator bi;
404	unsigned x;
405	EXECUTE_IF_SET_IN_BITMAP (pe1.members, 0, x, bi)
406	{
407	m_partial[x].ssa_base = op2;
408	m_partial[x].code = pe_min (t1: m_partial[x].code, t2: pe2.code);
409	}
410	bitmap_set_bit (pe1.members, v2);
411	return;
412	}
413	if (pe2.members)
414	{
415	// If there are no uses of op1, do not register.
416	if (has_zero_uses (var: op1))
417	return;
418	pe1.ssa_base = pe2.ssa_base;
419	// If pe2 is a 16 bit value, but only an 8 bit copy, we can't be any
420	// more than an 8 bit equivalence here, so choose MIN value.
421	pe1.code = pe_min (t1: r, t2: pe2.code);
422	pe1.members = pe2.members;
423	bitmap_set_bit (pe1.members, v1);
424	}
425	else
426	{
427	// If there are no uses of either operand, do not register.
428	if (has_zero_uses (var: op1) || has_zero_uses (var: op2))
429	return;
430	// Neither name has an entry, simply create op1 as slice of op2.
431	pe2.code = bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2)));
432	if (pe2.code == VREL_VARYING)
433	return;
434	pe2.ssa_base = op2;
435	pe2.members = BITMAP_ALLOC (obstack: &m_bitmaps);
436	bitmap_set_bit (pe2.members, v2);
437	pe1.ssa_base = op2;
438	pe1.code = r;
439	pe1.members = pe2.members;
440	bitmap_set_bit (pe1.members, v1);
441	}
442	}
443
444	// Return the set of partial equivalences associated with NAME. The bitmap
445	// will be NULL if there are none.
446
447	const pe_slice *
448	equiv_oracle::partial_equiv_set (tree name)
449	{
450	int v = SSA_NAME_VERSION (name);
451	if (v >= (int)m_partial.length ())
452	return NULL;
453	return &m_partial[v];
454	}
455
456	// Query if there is a partial equivalence between SSA1 and SSA2. Return
457	// VREL_VARYING if there is not one. If BASE is non-null, return the base
458	// ssa-name this is a slice of.
459
460	relation_kind
461	equiv_oracle::partial_equiv (tree ssa1, tree ssa2, tree *base) const
462	{
463	int v1 = SSA_NAME_VERSION (ssa1);
464	int v2 = SSA_NAME_VERSION (ssa2);
465
466	if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
467	return VREL_VARYING;
468
469	const pe_slice &pe1 = m_partial[v1];
470	const pe_slice &pe2 = m_partial[v2];
471	if (pe1.members && pe2.members == pe1.members)
472	{
473	if (base)
474	*base = pe1.ssa_base;
475	return pe_min (t1: pe1.code, t2: pe2.code);
476	}
477	return VREL_VARYING;
478	}
479
480
481	// Find and return the equivalency set for SSA along the dominators of BB.
482	// This is the external API.
483
484	const_bitmap
485	equiv_oracle::equiv_set (tree ssa, basic_block bb)
486	{
487	// Search the dominator tree for an equivalency.
488	equiv_chain *equiv = find_equiv_dom (name: ssa, bb);
489	if (equiv)
490	return equiv->m_names;
491
492	// Otherwise return a cached equiv set containing just this SSA.
493	unsigned v = SSA_NAME_VERSION (ssa);
494	if (v >= m_self_equiv.length ())
495	m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
496
497	if (!m_self_equiv[v])
498	{
499	m_self_equiv[v] = BITMAP_ALLOC (obstack: &m_bitmaps);
500	bitmap_set_bit (m_self_equiv[v], v);
501	}
502	return m_self_equiv[v];
503	}
504
505	// Query if there is a relation (equivalence) between 2 SSA_NAMEs.
506
507	relation_kind
508	equiv_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
509	{
510	// If the 2 ssa names share the same equiv set, they are equal.
511	if (equiv_set (ssa: ssa1, bb) == equiv_set (ssa: ssa2, bb))
512	return VREL_EQ;
513
514	// Check if there is a partial equivalence.
515	return partial_equiv (ssa1, ssa2);
516	}
517
518	// Query if there is a relation (equivalence) between 2 SSA_NAMEs.
519
520	relation_kind
521	equiv_oracle::query_relation (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1,
522	const_bitmap e2)
523	{
524	// If the 2 ssa names share the same equiv set, they are equal.
525	if (bitmap_equal_p (e1, e2))
526	return VREL_EQ;
527	return VREL_VARYING;
528	}
529
530	// If SSA has an equivalence in block BB, find and return it.
531	// Otherwise return NULL.
532
533	equiv_chain *
534	equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
535	{
536	if (bb >= (int)m_equiv.length () || !m_equiv[bb])
537	return NULL;
538
539	return m_equiv[bb]->find (ssa);
540	}
541
542	// Starting at block BB, walk the dominator chain looking for the nearest
543	// equivalence set containing NAME.
544
545	equiv_chain *
546	equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
547	{
548	unsigned v = SSA_NAME_VERSION (name);
549	// Short circuit looking for names which have no equivalences.
550	// Saves time looking for something which does not exist.
551	if (!bitmap_bit_p (m_equiv_set, v))
552	return NULL;
553
554	// NAME has at least once equivalence set, check to see if it has one along
555	// the dominator tree.
556	for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
557	{
558	equiv_chain *ptr = find_equiv_block (ssa: v, bb: bb->index);
559	if (ptr)
560	return ptr;
561	}
562	return NULL;
563	}
564
565	// Register equivalence between ssa_name V and set EQUIV in block BB,
566
567	bitmap
568	equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
569	{
570	// V will have an equivalency now.
571	bitmap_set_bit (m_equiv_set, v);
572
573	// If that equiv chain is in this block, simply use it.
574	if (equiv->m_bb == bb)
575	{
576	bitmap_set_bit (equiv->m_names, v);
577	bitmap_set_bit (m_equiv[bb->index]->m_names, v);
578	return NULL;
579	}
580
581	// Otherwise create an equivalence for this block which is a copy
582	// of equiv, the add V to the set.
583	bitmap b = BITMAP_ALLOC (obstack: &m_bitmaps);
584	valid_equivs (b, equivs: equiv->m_names, bb);
585	bitmap_set_bit (b, v);
586	return b;
587	}
588
589	// Register equivalence between set equiv_1 and equiv_2 in block BB.
590	// Return NULL if either name can be merged with the other. Otherwise
591	// return a pointer to the combined bitmap of names. This allows the
592	// caller to do any setup required for a new element.
593
594	bitmap
595	equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
596	equiv_chain *equiv_2)
597	{
598	// If equiv_1 is already in BB, use it as the combined set.
599	if (equiv_1->m_bb == bb)
600	{
601	valid_equivs (b: equiv_1->m_names, equivs: equiv_2->m_names, bb);
602	// Its hard to delete from a single linked list, so
603	// just clear the second one.
604	if (equiv_2->m_bb == bb)
605	bitmap_clear (equiv_2->m_names);
606	else
607	// Ensure the new names are in the summary for BB.
608	bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
609	return NULL;
610	}
611	// If equiv_2 is in BB, use it for the combined set.
612	if (equiv_2->m_bb == bb)
613	{
614	valid_equivs (b: equiv_2->m_names, equivs: equiv_1->m_names, bb);
615	// Ensure the new names are in the summary.
616	bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
617	return NULL;
618	}
619
620	// At this point, neither equivalence is from this block.
621	bitmap b = BITMAP_ALLOC (obstack: &m_bitmaps);
622	valid_equivs (b, equivs: equiv_1->m_names, bb);
623	valid_equivs (b, equivs: equiv_2->m_names, bb);
624	return b;
625	}
626
627	// Create an equivalency set containing only SSA in its definition block.
628	// This is done the first time SSA is registered in an equivalency and blocks
629	// any DOM searches past the definition.
630
631	void
632	equiv_oracle::register_initial_def (tree ssa)
633	{
634	if (SSA_NAME_IS_DEFAULT_DEF (ssa))
635	return;
636	basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
637	gcc_checking_assert (bb && !find_equiv_dom (ssa, bb));
638
639	unsigned v = SSA_NAME_VERSION (ssa);
640	bitmap_set_bit (m_equiv_set, v);
641	bitmap equiv_set = BITMAP_ALLOC (obstack: &m_bitmaps);
642	bitmap_set_bit (equiv_set, v);
643	add_equiv_to_block (bb, equiv: equiv_set);
644	}
645
646	// Register an equivalence between SSA1 and SSA2 in block BB.
647	// The equivalence oracle maintains a vector of equivalencies indexed by basic
648	// block. When an equivalence between SSA1 and SSA2 is registered in block BB,
649	// a query is made as to what equivalences both names have already, and
650	// any preexisting equivalences are merged to create a single equivalence
651	// containing all the ssa_names in this basic block.
652
653	void
654	equiv_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
655	tree ssa2)
656	{
657	// Process partial equivalencies.
658	if (relation_partial_equiv_p (r: k))
659	{
660	add_partial_equiv (r: k, op1: ssa1, op2: ssa2);
661	return;
662	}
663	// Only handle equality relations.
664	if (k != VREL_EQ)
665	return;
666
667	unsigned v1 = SSA_NAME_VERSION (ssa1);
668	unsigned v2 = SSA_NAME_VERSION (ssa2);
669
670	// If this is the first time an ssa_name has an equivalency registered
671	// create a self-equivalency record in the def block.
672	if (!bitmap_bit_p (m_equiv_set, v1))
673	register_initial_def (ssa: ssa1);
674	if (!bitmap_bit_p (m_equiv_set, v2))
675	register_initial_def (ssa: ssa2);
676
677	equiv_chain *equiv_1 = find_equiv_dom (name: ssa1, bb);
678	equiv_chain *equiv_2 = find_equiv_dom (name: ssa2, bb);
679
680	// Check if they are the same set
681	if (equiv_1 && equiv_1 == equiv_2)
682	return;
683
684	bitmap equiv_set;
685
686	// Case where we have 2 SSA_NAMEs that are not in any set.
687	if (!equiv_1 && !equiv_2)
688	{
689	bitmap_set_bit (m_equiv_set, v1);
690	bitmap_set_bit (m_equiv_set, v2);
691
692	equiv_set = BITMAP_ALLOC (obstack: &m_bitmaps);
693	bitmap_set_bit (equiv_set, v1);
694	bitmap_set_bit (equiv_set, v2);
695	}
696	else if (!equiv_1 && equiv_2)
697	equiv_set = register_equiv (bb, v: v1, equiv: equiv_2);
698	else if (equiv_1 && !equiv_2)
699	equiv_set = register_equiv (bb, v: v2, equiv: equiv_1);
700	else
701	equiv_set = register_equiv (bb, equiv_1, equiv_2);
702
703	// A non-null return is a bitmap that is to be added to the current
704	// block as a new equivalence.
705	if (!equiv_set)
706	return;
707
708	add_equiv_to_block (bb, equiv: equiv_set);
709	}
710
711	// Add an equivalency record in block BB containing bitmap EQUIV_SET.
712	// Note the internal caller is responsible for allocating EQUIV_SET properly.
713
714	void
715	equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
716	{
717	equiv_chain *ptr;
718
719	// Check if this is the first time a block has an equivalence added.
720	// and create a header block. And set the summary for this block.
721	if (!m_equiv[bb->index])
722	{
723	ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
724	sizeof (equiv_chain));
725	ptr->m_names = BITMAP_ALLOC (obstack: &m_bitmaps);
726	bitmap_copy (ptr->m_names, equiv_set);
727	ptr->m_bb = bb;
728	ptr->m_next = NULL;
729	m_equiv[bb->index] = ptr;
730	}
731
732	// Now create the element for this equiv set and initialize it.
733	ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
734	ptr->m_names = equiv_set;
735	ptr->m_bb = bb;
736	gcc_checking_assert (bb->index < (int)m_equiv.length ());
737	ptr->m_next = m_equiv[bb->index]->m_next;
738	m_equiv[bb->index]->m_next = ptr;
739	bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
740	}
741
742	// Make sure the BB vector is big enough and grow it if needed.
743
744	void
745	equiv_oracle::limit_check (basic_block bb)
746	{
747	int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
748	if (i >= (int)m_equiv.length ())
749	m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
750	}
751
752	// Dump the equivalence sets in BB to file F.
753
754	void
755	equiv_oracle::dump (FILE *f, basic_block bb) const
756	{
757	if (bb->index >= (int)m_equiv.length ())
758	return;
759	// Process equivalences.
760	if (m_equiv[bb->index])
761	{
762	equiv_chain *ptr = m_equiv[bb->index]->m_next;
763	for (; ptr; ptr = ptr->m_next)
764	ptr->dump (f);
765	}
766	// Look for partial equivalences defined in this block..
767	for (unsigned i = 0; i < num_ssa_names; i++)
768	{
769	tree name = ssa_name (i);
770	if (!gimple_range_ssa_p (exp: name) || !SSA_NAME_DEF_STMT (name))
771	continue;
772	if (i >= m_partial.length ())
773	break;
774	tree base = m_partial[i].ssa_base;
775	if (base && name != base && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb)
776	{
777	relation_kind k = partial_equiv (ssa1: name, ssa2: base);
778	if (k != VREL_VARYING)
779	{
780	value_relation vr (k, name, base);
781	fprintf (stream: f, format: "Partial equiv ");
782	vr.dump (f);
783	fputc (c: '\n',stream: f);
784	}
785	}
786	}
787	}
788
789	// Dump all equivalence sets known to the oracle.
790
791	void
792	equiv_oracle::dump (FILE *f) const
793	{
794	fprintf (stream: f, format: "Equivalency dump\n");
795	for (unsigned i = 0; i < m_equiv.length (); i++)
796	if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
797	{
798	fprintf (stream: f, format: "BB%d\n", i);
799	dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
800	}
801	}
802
803
804	// --------------------------------------------------------------------------
805	// Negate the current relation.
806
807	void
808	value_relation::negate ()
809	{
810	related = relation_negate (r: related);
811	}
812
813	// Perform an intersection between 2 relations. *this &&= p.
814
815	bool
816	value_relation::intersect (value_relation &p)
817	{
818	// Save previous value
819	relation_kind old = related;
820
821	if (p.op1 () == op1 () && p.op2 () == op2 ())
822	related = relation_intersect (r1: kind (), r2: p.kind ());
823	else if (p.op2 () == op1 () && p.op1 () == op2 ())
824	related = relation_intersect (r1: kind (), r2: relation_swap (r: p.kind ()));
825	else
826	return false;
827
828	return old != related;
829	}
830
831	// Perform a union between 2 relations. *this ||= p.
832
833	bool
834	value_relation::union_ (value_relation &p)
835	{
836	// Save previous value
837	relation_kind old = related;
838
839	if (p.op1 () == op1 () && p.op2 () == op2 ())
840	related = relation_union (r1: kind(), r2: p.kind());
841	else if (p.op2 () == op1 () && p.op1 () == op2 ())
842	related = relation_union (r1: kind(), r2: relation_swap (r: p.kind ()));
843	else
844	return false;
845
846	return old != related;
847	}
848
849	// Identify and apply any transitive relations between REL
850	// and THIS. Return true if there was a transformation.
851
852	bool
853	value_relation::apply_transitive (const value_relation &rel)
854	{
855	relation_kind k = VREL_VARYING;
856
857	// Identify any common operand, and normalize the relations to
858	// the form : A < B B < C produces A < C
859	if (rel.op1 () == name2)
860	{
861	// A < B B < C
862	if (rel.op2 () == name1)
863	return false;
864	k = relation_transitive (r1: kind (), r2: rel.kind ());
865	if (k != VREL_VARYING)
866	{
867	related = k;
868	name2 = rel.op2 ();
869	return true;
870	}
871	}
872	else if (rel.op1 () == name1)
873	{
874	// B > A B < C
875	if (rel.op2 () == name2)
876	return false;
877	k = relation_transitive (r1: relation_swap (r: kind ()), r2: rel.kind ());
878	if (k != VREL_VARYING)
879	{
880	related = k;
881	name1 = name2;
882	name2 = rel.op2 ();
883	return true;
884	}
885	}
886	else if (rel.op2 () == name2)
887	{
888	// A < B C > B
889	if (rel.op1 () == name1)
890	return false;
891	k = relation_transitive (r1: kind (), r2: relation_swap (r: rel.kind ()));
892	if (k != VREL_VARYING)
893	{
894	related = k;
895	name2 = rel.op1 ();
896	return true;
897	}
898	}
899	else if (rel.op2 () == name1)
900	{
901	// B > A C > B
902	if (rel.op1 () == name2)
903	return false;
904	k = relation_transitive (r1: relation_swap (r: kind ()),
905	r2: relation_swap (r: rel.kind ()));
906	if (k != VREL_VARYING)
907	{
908	related = k;
909	name1 = name2;
910	name2 = rel.op1 ();
911	return true;
912	}
913	}
914	return false;
915	}
916
917	// Create a trio from this value relation given LHS, OP1 and OP2.
918
919	relation_trio
920	value_relation::create_trio (tree lhs, tree op1, tree op2)
921	{
922	relation_kind lhs_1;
923	if (lhs == name1 && op1 == name2)
924	lhs_1 = related;
925	else if (lhs == name2 && op1 == name1)
926	lhs_1 = relation_swap (r: related);
927	else
928	lhs_1 = VREL_VARYING;
929
930	relation_kind lhs_2;
931	if (lhs == name1 && op2 == name2)
932	lhs_2 = related;
933	else if (lhs == name2 && op2 == name1)
934	lhs_2 = relation_swap (r: related);
935	else
936	lhs_2 = VREL_VARYING;
937
938	relation_kind op_op;
939	if (op1 == name1 && op2 == name2)
940	op_op = related;
941	else if (op1 == name2 && op2 == name1)
942	op_op = relation_swap (r: related);
943	else if (op1 == op2)
944	op_op = VREL_EQ;
945	else
946	op_op = VREL_VARYING;
947
948	return relation_trio (lhs_1, lhs_2, op_op);
949	}
950
951	// Dump the relation to file F.
952
953	void
954	value_relation::dump (FILE *f) const
955	{
956	if (!name1 || !name2)
957	{
958	fprintf (stream: f, format: "no relation registered");
959	return;
960	}
961	fputc (c: '(', stream: f);
962	print_generic_expr (f, op1 (), TDF_SLIM);
963	print_relation (f, rel: kind ());
964	print_generic_expr (f, op2 (), TDF_SLIM);
965	fputc(c: ')', stream: f);
966	}
967
968	// This container is used to link relations in a chain.
969
970	class relation_chain : public value_relation
971	{
972	public:
973	relation_chain *m_next;
974	};
975
976	// ------------------------------------------------------------------------
977
978	// Find the relation between any ssa_name in B1 and any name in B2 in LIST.
979	// This will allow equivalencies to be applied to any SSA_NAME in a relation.
980
981	relation_kind
982	relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
983	{
984	if (!m_names)
985	return VREL_VARYING;
986
987	// If both b1 and b2 aren't referenced in this block, cant be a relation
988	if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
989	return VREL_VARYING;
990
991	// Search for the first relation that contains BOTH an element from B1
992	// and B2, and return that relation.
993	for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
994	{
995	unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
996	unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
997	if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
998	return ptr->kind ();
999	if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
1000	return relation_swap (r: ptr->kind ());
1001	}
1002
1003	return VREL_VARYING;
1004	}
1005
1006	// Instantiate a relation oracle.
1007
1008	dom_oracle::dom_oracle ()
1009	{
1010	m_relations.create (nelems: 0);
1011	m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1012	m_relation_set = BITMAP_ALLOC (obstack: &m_bitmaps);
1013	m_tmp = BITMAP_ALLOC (obstack: &m_bitmaps);
1014	m_tmp2 = BITMAP_ALLOC (obstack: &m_bitmaps);
1015	}
1016
1017	// Destruct a relation oracle.
1018
1019	dom_oracle::~dom_oracle ()
1020	{
1021	m_relations.release ();
1022	}
1023
1024	// Register relation K between ssa_name OP1 and OP2 on STMT.
1025
1026	void
1027	relation_oracle::register_stmt (gimple *stmt, relation_kind k, tree op1,
1028	tree op2)
1029	{
1030	gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1031	gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1032	gcc_checking_assert (stmt && gimple_bb (stmt));
1033
1034	// Don't register lack of a relation.
1035	if (k == VREL_VARYING)
1036	return;
1037
1038	if (dump_file && (dump_flags & TDF_DETAILS))
1039	{
1040	value_relation vr (k, op1, op2);
1041	fprintf (stream: dump_file, format: " Registering value_relation ");
1042	vr.dump (f: dump_file);
1043	fprintf (stream: dump_file, format: " (bb%d) at ", gimple_bb (g: stmt)->index);
1044	print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1045	}
1046
1047	// If an equivalence is being added between a PHI and one of its arguments
1048	// make sure that that argument is not defined in the same block.
1049	// This can happen along back edges and the equivalence will not be
1050	// applicable as it would require a use before def.
1051	if (k == VREL_EQ && is_a<gphi *> (p: stmt))
1052	{
1053	tree phi_def = gimple_phi_result (gs: stmt);
1054	gcc_checking_assert (phi_def == op1 || phi_def == op2);
1055	tree arg = op2;
1056	if (phi_def == op2)
1057	arg = op1;
1058	if (gimple_bb (g: stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
1059	{
1060	if (dump_file && (dump_flags & TDF_DETAILS))
1061	{
1062	fprintf (stream: dump_file, format: " Not registered due to ");
1063	print_generic_expr (dump_file, arg, TDF_SLIM);
1064	fprintf (stream: dump_file, format: " being defined in the same block.\n");
1065	}
1066	return;
1067	}
1068	}
1069	register_relation (gimple_bb (g: stmt), k, op1, op2);
1070	}
1071
1072	// Register relation K between ssa_name OP1 and OP2 on edge E.
1073
1074	void
1075	relation_oracle::register_edge (edge e, relation_kind k, tree op1, tree op2)
1076	{
1077	gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1078	gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1079
1080	// Do not register lack of relation, or blocks which have more than
1081	// edge E for a predecessor.
1082	if (k == VREL_VARYING || !single_pred_p (bb: e->dest))
1083	return;
1084
1085	if (dump_file && (dump_flags & TDF_DETAILS))
1086	{
1087	value_relation vr (k, op1, op2);
1088	fprintf (stream: dump_file, format: " Registering value_relation ");
1089	vr.dump (f: dump_file);
1090	fprintf (stream: dump_file, format: " on (%d->%d)\n", e->src->index, e->dest->index);
1091	}
1092
1093	register_relation (e->dest, k, op1, op2);
1094	}
1095
1096	// Register relation K between OP! and OP2 in block BB.
1097	// This creates the record and searches for existing records in the dominator
1098	// tree to merge with.
1099
1100	void
1101	dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
1102	tree op2)
1103	{
1104	// If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1105	// and no other relation makes sense.
1106	if (op1 == op2)
1107	return;
1108
1109	// Equivalencies are handled by the equivalence oracle.
1110	if (relation_equiv_p (r: k))
1111	equiv_oracle::register_relation (bb, k, ssa1: op1, ssa2: op2);
1112	else
1113	{
1114	// if neither op1 nor op2 are in a relation before this is registered,
1115	// there will be no transitive.
1116	bool check = bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op1))
1117	|| bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op2));
1118	relation_chain *ptr = set_one_relation (bb, k, op1, op2);
1119	if (ptr && check)
1120	register_transitives (bb, *ptr);
1121	}
1122	}
1123
1124	// Register relation K between OP! and OP2 in block BB.
1125	// This creates the record and searches for existing records in the dominator
1126	// tree to merge with. Return the record, or NULL if no record was created.
1127
1128	relation_chain *
1129	dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1,
1130	tree op2)
1131	{
1132	gcc_checking_assert (k != VREL_VARYING && k != VREL_EQ);
1133
1134	value_relation vr(k, op1, op2);
1135	int bbi = bb->index;
1136
1137	if (bbi >= (int)m_relations.length())
1138	m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1139
1140	// Summary bitmap indicating what ssa_names have relations in this BB.
1141	bitmap bm = m_relations[bbi].m_names;
1142	if (!bm)
1143	bm = m_relations[bbi].m_names = BITMAP_ALLOC (obstack: &m_bitmaps);
1144	unsigned v1 = SSA_NAME_VERSION (op1);
1145	unsigned v2 = SSA_NAME_VERSION (op2);
1146
1147	relation_kind curr;
1148	relation_chain *ptr;
1149	curr = find_relation_block (bb: bbi, v1, v2, obj: &ptr);
1150	// There is an existing relation in this block, just intersect with it.
1151	if (curr != VREL_VARYING)
1152	{
1153	if (dump_file && (dump_flags & TDF_DETAILS))
1154	{
1155	fprintf (stream: dump_file, format: " Intersecting with existing ");
1156	ptr->dump (f: dump_file);
1157	}
1158	// Check into whether we can simply replace the relation rather than
1159	// intersecting it. This may help with some optimistic iterative
1160	// updating algorithms.
1161	bool new_rel = ptr->intersect (p&: vr);
1162	if (dump_file && (dump_flags & TDF_DETAILS))
1163	{
1164	fprintf (stream: dump_file, format: " to produce ");
1165	ptr->dump (f: dump_file);
1166	fprintf (stream: dump_file, format: " %s.\n", new_rel ? "Updated" : "No Change");
1167	}
1168	// If there was no change, return no record..
1169	if (!new_rel)
1170	return NULL;
1171	}
1172	else
1173	{
1174	if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
1175	{
1176	if (dump_file && (dump_flags & TDF_DETAILS))
1177	fprintf (stream: dump_file, format: " Not registered due to bb being full\n");
1178	return NULL;
1179	}
1180	m_relations[bbi].m_num_relations++;
1181	// Check for an existing relation further up the DOM chain.
1182	// By including dominating relations, The first one found in any search
1183	// will be the aggregate of all the previous ones.
1184	curr = find_relation_dom (bb, v1, v2);
1185	if (curr != VREL_VARYING)
1186	k = relation_intersect (r1: curr, r2: k);
1187
1188	bitmap_set_bit (bm, v1);
1189	bitmap_set_bit (bm, v2);
1190	bitmap_set_bit (m_relation_set, v1);
1191	bitmap_set_bit (m_relation_set, v2);
1192
1193	ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1194	sizeof (relation_chain));
1195	ptr->set_relation (r: k, n1: op1, n2: op2);
1196	ptr->m_next = m_relations[bbi].m_head;
1197	m_relations[bbi].m_head = ptr;
1198	}
1199	return ptr;
1200	}
1201
1202	// Starting at ROOT_BB search the DOM tree looking for relations which
1203	// may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
1204	// bitmaps for op1/op2 and any of their equivalences that should also be
1205	// considered.
1206
1207	void
1208	dom_oracle::register_transitives (basic_block root_bb,
1209	const value_relation &relation)
1210	{
1211	basic_block bb;
1212	// Only apply transitives to certain kinds of operations.
1213	switch (relation.kind ())
1214	{
1215	case VREL_LE:
1216	case VREL_LT:
1217	case VREL_GT:
1218	case VREL_GE:
1219	break;
1220	default:
1221	return;
1222	}
1223
1224	const_bitmap equiv1 = equiv_set (ssa: relation.op1 (), bb: root_bb);
1225	const_bitmap equiv2 = equiv_set (ssa: relation.op2 (), bb: root_bb);
1226
1227	for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1228	{
1229	int bbi = bb->index;
1230	if (bbi >= (int)m_relations.length())
1231	continue;
1232	const_bitmap bm = m_relations[bbi].m_names;
1233	if (!bm)
1234	continue;
1235	if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
1236	continue;
1237	// At least one of the 2 ops has a relation in this block.
1238	relation_chain *ptr;
1239	for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
1240	{
1241	// In the presence of an equivalence, 2 operands may do not
1242	// naturally match. ie with equivalence a_2 == b_3
1243	// given c_1 < a_2 && b_3 < d_4
1244	// convert the second relation (b_3 < d_4) to match any
1245	// equivalences to found in the first relation.
1246	// ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1247	// transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1248
1249	tree r1, r2;
1250	tree p1 = ptr->op1 ();
1251	tree p2 = ptr->op2 ();
1252	// Find which equivalence is in the first operand.
1253	if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
1254	r1 = p1;
1255	else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
1256	r1 = p2;
1257	else
1258	r1 = NULL_TREE;
1259
1260	// Find which equivalence is in the second operand.
1261	if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
1262	r2 = p1;
1263	else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
1264	r2 = p2;
1265	else
1266	r2 = NULL_TREE;
1267
1268	// Ignore if both NULL (not relevant relation) or the same,
1269	if (r1 == r2)
1270	continue;
1271
1272	// Any operand not an equivalence, just take the real operand.
1273	if (!r1)
1274	r1 = relation.op1 ();
1275	if (!r2)
1276	r2 = relation.op2 ();
1277
1278	value_relation nr (relation.kind (), r1, r2);
1279	if (nr.apply_transitive (rel: *ptr))
1280	{
1281	if (!set_one_relation (bb: root_bb, k: nr.kind (), op1: nr.op1 (), op2: nr.op2 ()))
1282	return;
1283	if (dump_file && (dump_flags & TDF_DETAILS))
1284	{
1285	fprintf (stream: dump_file, format: " Registering transitive relation ");
1286	nr.dump (f: dump_file);
1287	fputc (c: '\n', stream: dump_file);
1288	}
1289	}
1290
1291	}
1292	}
1293	}
1294
1295	// Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1296	// This will allow equivalencies to be applied to any SSA_NAME in a relation.
1297
1298	relation_kind
1299	dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
1300	const_bitmap b2) const
1301	{
1302	if (bb >= m_relations.length())
1303	return VREL_VARYING;
1304
1305	return m_relations[bb].find_relation (b1, b2);
1306	}
1307
1308	// Search the DOM tree for a relation between an element of equivalency set B1
1309	// and B2, starting with block BB.
1310
1311	relation_kind
1312	dom_oracle::query_relation (basic_block bb, const_bitmap b1,
1313	const_bitmap b2)
1314	{
1315	relation_kind r;
1316	if (bitmap_equal_p (b1, b2))
1317	return VREL_EQ;
1318
1319	// If either name does not occur in a relation anywhere, there isn't one.
1320	if (!bitmap_intersect_p (m_relation_set, b1)
1321	|| !bitmap_intersect_p (m_relation_set, b2))
1322	return VREL_VARYING;
1323
1324	// Search each block in the DOM tree checking.
1325	for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1326	{
1327	r = find_relation_block (bb: bb->index, b1, b2);
1328	if (r != VREL_VARYING)
1329	return r;
1330	}
1331	return VREL_VARYING;
1332
1333	}
1334
1335	// Find a relation in block BB between ssa version V1 and V2. If a relation
1336	// is found, return a pointer to the chain object in OBJ.
1337
1338	relation_kind
1339	dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
1340	relation_chain **obj) const
1341	{
1342	if (bb >= (int)m_relations.length())
1343	return VREL_VARYING;
1344
1345	const_bitmap bm = m_relations[bb].m_names;
1346	if (!bm)
1347	return VREL_VARYING;
1348
1349	// If both b1 and b2 aren't referenced in this block, cant be a relation
1350	if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1351	return VREL_VARYING;
1352
1353	relation_chain *ptr;
1354	for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1355	{
1356	unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1357	unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1358	if (v1 == op1 && v2 == op2)
1359	{
1360	if (obj)
1361	*obj = ptr;
1362	return ptr->kind ();
1363	}
1364	if (v1 == op2 && v2 == op1)
1365	{
1366	if (obj)
1367	*obj = ptr;
1368	return relation_swap (r: ptr->kind ());
1369	}
1370	}
1371
1372	return VREL_VARYING;
1373	}
1374
1375	// Find a relation between SSA version V1 and V2 in the dominator tree
1376	// starting with block BB
1377
1378	relation_kind
1379	dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const
1380	{
1381	relation_kind r;
1382	// IF either name does not occur in a relation anywhere, there isn't one.
1383	if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1384	return VREL_VARYING;
1385
1386	for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1387	{
1388	r = find_relation_block (bb: bb->index, v1, v2);
1389	if (r != VREL_VARYING)
1390	return r;
1391	}
1392	return VREL_VARYING;
1393
1394	}
1395
1396	// Query if there is a relation between SSA1 and SS2 in block BB or a
1397	// dominator of BB
1398
1399	relation_kind
1400	dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1401	{
1402	relation_kind kind;
1403	unsigned v1 = SSA_NAME_VERSION (ssa1);
1404	unsigned v2 = SSA_NAME_VERSION (ssa2);
1405	if (v1 == v2)
1406	return VREL_EQ;
1407
1408	// If v1 or v2 do not have any relations or equivalences, a partial
1409	// equivalence is the only possibility.
1410	if ((!bitmap_bit_p (m_relation_set, v1) && !has_equiv_p (v: v1))
1411	|| (!bitmap_bit_p (m_relation_set, v2) && !has_equiv_p (v: v2)))
1412	return partial_equiv (ssa1, ssa2);
1413
1414	// Check for equivalence first. They must be in each equivalency set.
1415	const_bitmap equiv1 = equiv_set (ssa: ssa1, bb);
1416	const_bitmap equiv2 = equiv_set (ssa: ssa2, bb);
1417	if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
1418	return VREL_EQ;
1419
1420	kind = partial_equiv (ssa1, ssa2);
1421	if (kind != VREL_VARYING)
1422	return kind;
1423
1424	// Initially look for a direct relationship and just return that.
1425	kind = find_relation_dom (bb, v1, v2);
1426	if (kind != VREL_VARYING)
1427	return kind;
1428
1429	// Query using the equivalence sets.
1430	kind = query_relation (bb, b1: equiv1, b2: equiv2);
1431	return kind;
1432	}
1433
1434	// Dump all the relations in block BB to file F.
1435
1436	void
1437	dom_oracle::dump (FILE *f, basic_block bb) const
1438	{
1439	equiv_oracle::dump (f,bb);
1440
1441	if (bb->index >= (int)m_relations.length ())
1442	return;
1443	if (!m_relations[bb->index].m_names)
1444	return;
1445
1446	relation_chain *ptr = m_relations[bb->index].m_head;
1447	for (; ptr; ptr = ptr->m_next)
1448	{
1449	fprintf (stream: f, format: "Relational : ");
1450	ptr->dump (f);
1451	fprintf (stream: f, format: "\n");
1452	}
1453	}
1454
1455	// Dump all the relations known to file F.
1456
1457	void
1458	dom_oracle::dump (FILE *f) const
1459	{
1460	fprintf (stream: f, format: "Relation dump\n");
1461	for (unsigned i = 0; i < m_relations.length (); i++)
1462	if (BASIC_BLOCK_FOR_FN (cfun, i))
1463	{
1464	fprintf (stream: f, format: "BB%d\n", i);
1465	dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
1466	}
1467	}
1468
1469	void
1470	relation_oracle::debug () const
1471	{
1472	dump (stderr);
1473	}
1474
1475	path_oracle::path_oracle (relation_oracle *oracle)
1476	{
1477	set_root_oracle (oracle);
1478	bitmap_obstack_initialize (&m_bitmaps);
1479	obstack_init (&m_chain_obstack);
1480
1481	// Initialize header records.
1482	m_equiv.m_names = BITMAP_ALLOC (obstack: &m_bitmaps);
1483	m_equiv.m_bb = NULL;
1484	m_equiv.m_next = NULL;
1485	m_relations.m_names = BITMAP_ALLOC (obstack: &m_bitmaps);
1486	m_relations.m_head = NULL;
1487	m_killed_defs = BITMAP_ALLOC (obstack: &m_bitmaps);
1488	}
1489
1490	path_oracle::~path_oracle ()
1491	{
1492	obstack_free (&m_chain_obstack, NULL);
1493	bitmap_obstack_release (&m_bitmaps);
1494	}
1495
1496	// Return the equiv set for SSA, and if there isn't one, check for equivs
1497	// starting in block BB.
1498
1499	const_bitmap
1500	path_oracle::equiv_set (tree ssa, basic_block bb)
1501	{
1502	// Check the list first.
1503	equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
1504	if (ptr)
1505	return ptr->m_names;
1506
1507	// Otherwise defer to the root oracle.
1508	if (m_root)
1509	return m_root->equiv_set (ssa, bb);
1510
1511	// Allocate a throw away bitmap if there isn't a root oracle.
1512	bitmap tmp = BITMAP_ALLOC (obstack: &m_bitmaps);
1513	bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
1514	return tmp;
1515	}
1516
1517	// Register an equivalence between SSA1 and SSA2 resolving unknowns from
1518	// block BB.
1519
1520	void
1521	path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
1522	{
1523	const_bitmap equiv_1 = equiv_set (ssa: ssa1, bb);
1524	const_bitmap equiv_2 = equiv_set (ssa: ssa2, bb);
1525
1526	// Check if they are the same set, if so, we're done.
1527	if (bitmap_equal_p (equiv_1, equiv_2))
1528	return;
1529
1530	// Don't mess around, simply create a new record and insert it first.
1531	bitmap b = BITMAP_ALLOC (obstack: &m_bitmaps);
1532	valid_equivs (b, equivs: equiv_1, bb);
1533	valid_equivs (b, equivs: equiv_2, bb);
1534
1535	equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1536	sizeof (equiv_chain));
1537	ptr->m_names = b;
1538	ptr->m_bb = NULL;
1539	ptr->m_next = m_equiv.m_next;
1540	m_equiv.m_next = ptr;
1541	bitmap_ior_into (m_equiv.m_names, b);
1542	}
1543
1544	// Register killing definition of an SSA_NAME.
1545
1546	void
1547	path_oracle::killing_def (tree ssa)
1548	{
1549	if (dump_file && (dump_flags & TDF_DETAILS))
1550	{
1551	fprintf (stream: dump_file, format: " Registering killing_def (path_oracle) ");
1552	print_generic_expr (dump_file, ssa, TDF_SLIM);
1553	fprintf (stream: dump_file, format: "\n");
1554	}
1555
1556	unsigned v = SSA_NAME_VERSION (ssa);
1557
1558	bitmap_set_bit (m_killed_defs, v);
1559	bitmap_set_bit (m_equiv.m_names, v);
1560
1561	// Now add an equivalency with itself so we don't look to the root oracle.
1562	bitmap b = BITMAP_ALLOC (obstack: &m_bitmaps);
1563	bitmap_set_bit (b, v);
1564	equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1565	sizeof (equiv_chain));
1566	ptr->m_names = b;
1567	ptr->m_bb = NULL;
1568	ptr->m_next = m_equiv.m_next;
1569	m_equiv.m_next = ptr;
1570
1571	// Walk the relation list and remove SSA from any relations.
1572	if (!bitmap_bit_p (m_relations.m_names, v))
1573	return;
1574
1575	bitmap_clear_bit (m_relations.m_names, v);
1576	relation_chain **prev = &(m_relations.m_head);
1577	relation_chain *next = NULL;
1578	for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
1579	{
1580	gcc_checking_assert (*prev == ptr);
1581	next = ptr->m_next;
1582	if (SSA_NAME_VERSION (ptr->op1 ()) == v
1583	|| SSA_NAME_VERSION (ptr->op2 ()) == v)
1584	*prev = ptr->m_next;
1585	else
1586	prev = &(ptr->m_next);
1587	}
1588	}
1589
1590	// Register relation K between SSA1 and SSA2, resolving unknowns by
1591	// querying from BB.
1592
1593	void
1594	path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
1595	tree ssa2)
1596	{
1597	// If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1598	// and no other relation makes sense.
1599	if (ssa1 == ssa2)
1600	return;
1601
1602	if (dump_file && (dump_flags & TDF_DETAILS))
1603	{
1604	value_relation vr (k, ssa1, ssa2);
1605	fprintf (stream: dump_file, format: " Registering value_relation (path_oracle) ");
1606	vr.dump (f: dump_file);
1607	fprintf (stream: dump_file, format: " (root: bb%d)\n", bb->index);
1608	}
1609
1610	relation_kind curr = query_relation (bb, ssa1, ssa2);
1611	if (curr != VREL_VARYING)
1612	k = relation_intersect (r1: curr, r2: k);
1613
1614	if (k == VREL_EQ)
1615	{
1616	register_equiv (bb, ssa1, ssa2);
1617	return;
1618	}
1619
1620	bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
1621	bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
1622	relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1623	sizeof (relation_chain));
1624	ptr->set_relation (r: k, n1: ssa1, n2: ssa2);
1625	ptr->m_next = m_relations.m_head;
1626	m_relations.m_head = ptr;
1627	}
1628
1629	// Query for a relationship between equiv set B1 and B2, resolving unknowns
1630	// starting at block BB.
1631
1632	relation_kind
1633	path_oracle::query_relation (basic_block bb, const_bitmap b1, const_bitmap b2)
1634	{
1635	if (bitmap_equal_p (b1, b2))
1636	return VREL_EQ;
1637
1638	relation_kind k = m_relations.find_relation (b1, b2);
1639
1640	// Do not look at the root oracle for names that have been killed
1641	// along the path.
1642	if (bitmap_intersect_p (m_killed_defs, b1)
1643	|| bitmap_intersect_p (m_killed_defs, b2))
1644	return k;
1645
1646	if (k == VREL_VARYING && m_root)
1647	k = m_root->query_relation (bb, b1, b2);
1648
1649	return k;
1650	}
1651
1652	// Query for a relationship between SSA1 and SSA2, resolving unknowns
1653	// starting at block BB.
1654
1655	relation_kind
1656	path_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1657	{
1658	unsigned v1 = SSA_NAME_VERSION (ssa1);
1659	unsigned v2 = SSA_NAME_VERSION (ssa2);
1660
1661	if (v1 == v2)
1662	return VREL_EQ;
1663
1664	const_bitmap equiv_1 = equiv_set (ssa: ssa1, bb);
1665	const_bitmap equiv_2 = equiv_set (ssa: ssa2, bb);
1666	if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
1667	return VREL_EQ;
1668
1669	return query_relation (bb, b1: equiv_1, b2: equiv_2);
1670	}
1671
1672	// Reset any relations registered on this path. ORACLE is the root
1673	// oracle to use.
1674
1675	void
1676	path_oracle::reset_path (relation_oracle *oracle)
1677	{
1678	set_root_oracle (oracle);
1679	m_equiv.m_next = NULL;
1680	bitmap_clear (m_equiv.m_names);
1681	m_relations.m_head = NULL;
1682	bitmap_clear (m_relations.m_names);
1683	bitmap_clear (m_killed_defs);
1684	}
1685
1686	// Dump relation in basic block... Do nothing here.
1687
1688	void
1689	path_oracle::dump (FILE *, basic_block) const
1690	{
1691	}
1692
1693	// Dump the relations and equivalencies found in the path.
1694
1695	void
1696	path_oracle::dump (FILE *f) const
1697	{
1698	equiv_chain *ptr = m_equiv.m_next;
1699	relation_chain *ptr2 = m_relations.m_head;
1700
1701	if (ptr || ptr2)
1702	fprintf (stream: f, format: "\npath_oracle:\n");
1703
1704	for (; ptr; ptr = ptr->m_next)
1705	ptr->dump (f);
1706
1707	for (; ptr2; ptr2 = ptr2->m_next)
1708	{
1709	fprintf (stream: f, format: "Relational : ");
1710	ptr2->dump (f);
1711	fprintf (stream: f, format: "\n");
1712	}
1713	}
1714
1715	// ------------------------------------------------------------------------
1716	// EQUIV iterator. Although we have bitmap iterators, don't expose that it
1717	// is currently a bitmap. Use an export iterator to hide future changes.
1718
1719	// Construct a basic iterator over an equivalence bitmap.
1720
1721	equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle,
1722	basic_block bb, tree name,
1723	bool full, bool partial)
1724	{
1725	m_name = name;
1726	m_oracle = oracle;
1727	m_pe = partial ? oracle->partial_equiv_set (name) : NULL;
1728	m_bm = NULL;
1729	if (full)
1730	m_bm = oracle->equiv_set (name, bb);
1731	if (!m_bm && m_pe)
1732	m_bm = m_pe->members;
1733	if (m_bm)
1734	bmp_iter_set_init (bi: &m_bi, map: m_bm, start_bit: 1, bit_no: &m_y);
1735	}
1736
1737	// Move to the next export bitmap spot.
1738
1739	void
1740	equiv_relation_iterator::next ()
1741	{
1742	bmp_iter_next (bi: &m_bi, bit_no: &m_y);
1743	}
1744
1745	// Fetch the name of the next export in the export list. Return NULL if
1746	// iteration is done.
1747
1748	tree
1749	equiv_relation_iterator::get_name (relation_kind *rel)
1750	{
1751	if (!m_bm)
1752	return NULL_TREE;
1753
1754	while (bmp_iter_set (bi: &m_bi, bit_no: &m_y))
1755	{
1756	// Do not return self.
1757	tree t = ssa_name (m_y);
1758	if (t && t != m_name)
1759	{
1760	relation_kind k = VREL_EQ;
1761	if (m_pe && m_bm == m_pe->members)
1762	{
1763	const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t);
1764	if (equiv_pe && equiv_pe->members == m_pe->members)
1765	k = pe_min (t1: m_pe->code, t2: equiv_pe->code);
1766	else
1767	k = VREL_VARYING;
1768	}
1769	if (relation_equiv_p (r: k))
1770	{
1771	if (rel)
1772	*rel = k;
1773	return t;
1774	}
1775	}
1776	next ();
1777	}
1778
1779	// Process partial equivs after full equivs if both were requested.
1780	if (m_pe && m_bm != m_pe->members)
1781	{
1782	m_bm = m_pe->members;
1783	if (m_bm)
1784	{
1785	// Recursively call back to process First PE.
1786	bmp_iter_set_init (bi: &m_bi, map: m_bm, start_bit: 1, bit_no: &m_y);
1787	return get_name (rel);
1788	}
1789	}
1790	return NULL_TREE;
1791	}
1792
1793	#if CHECKING_P
1794	#include "selftest.h"
1795
1796	namespace selftest
1797	{
1798	void
1799	relation_tests ()
1800	{
1801	// rr_*_table tables use unsigned char rather than relation_kind.
1802	ASSERT_LT (VREL_LAST, UCHAR_MAX);
1803	// Verify commutativity of relation_intersect and relation_union.
1804	for (relation_kind r1 = VREL_VARYING; r1 < VREL_PE8;
1805	r1 = relation_kind (r1 + 1))
1806	for (relation_kind r2 = VREL_VARYING; r2 < VREL_PE8;
1807	r2 = relation_kind (r2 + 1))
1808	{
1809	ASSERT_EQ (relation_intersect (r1, r2), relation_intersect (r2, r1));
1810	ASSERT_EQ (relation_union (r1, r2), relation_union (r2, r1));
1811	}
1812	}
1813
1814	} // namespace selftest
1815
1816	#endif // CHECKING_P
1817