1/* Header file for the value range relational processing.
2 Copyright (C) 2020-2024 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
35static 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
41void
42print_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).
48static 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
54relation_kind
55relation_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.
61static 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
67relation_kind
68relation_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
75static 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
104relation_kind
105relation_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
113static 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
141relation_kind
142relation_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
151static 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
180relation_kind
181relation_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
190void
191adjust_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
207static 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
220relation_kind
221relation_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
261relation_kind
262relation_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
274void
275relation_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
304equiv_chain *
305equiv_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
321void
322equiv_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
345equiv_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
360equiv_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
371void
372equiv_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
447const pe_slice *
448equiv_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
460relation_kind
461equiv_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
484const_bitmap
485equiv_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
507relation_kind
508equiv_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
520relation_kind
521equiv_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
533equiv_chain *
534equiv_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
545equiv_chain *
546equiv_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
567bitmap
568equiv_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
594bitmap
595equiv_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
631void
632equiv_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
653void
654equiv_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
714void
715equiv_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 limit_check (bb);
722 if (!m_equiv[bb->index])
723 {
724 ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
725 sizeof (equiv_chain));
726 ptr->m_names = BITMAP_ALLOC (obstack: &m_bitmaps);
727 bitmap_copy (ptr->m_names, equiv_set);
728 ptr->m_bb = bb;
729 ptr->m_next = NULL;
730 m_equiv[bb->index] = ptr;
731 }
732
733 // Now create the element for this equiv set and initialize it.
734 ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
735 ptr->m_names = equiv_set;
736 ptr->m_bb = bb;
737 gcc_checking_assert (bb->index < (int)m_equiv.length ());
738 ptr->m_next = m_equiv[bb->index]->m_next;
739 m_equiv[bb->index]->m_next = ptr;
740 bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
741}
742
743// Make sure the BB vector is big enough and grow it if needed.
744
745void
746equiv_oracle::limit_check (basic_block bb)
747{
748 int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
749 if (i >= (int)m_equiv.length ())
750 m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
751}
752
753// Dump the equivalence sets in BB to file F.
754
755void
756equiv_oracle::dump (FILE *f, basic_block bb) const
757{
758 if (bb->index >= (int)m_equiv.length ())
759 return;
760 // Process equivalences.
761 if (m_equiv[bb->index])
762 {
763 equiv_chain *ptr = m_equiv[bb->index]->m_next;
764 for (; ptr; ptr = ptr->m_next)
765 ptr->dump (f);
766 }
767 // Look for partial equivalences defined in this block..
768 for (unsigned i = 0; i < num_ssa_names; i++)
769 {
770 tree name = ssa_name (i);
771 if (!gimple_range_ssa_p (exp: name) || !SSA_NAME_DEF_STMT (name))
772 continue;
773 if (i >= m_partial.length ())
774 break;
775 tree base = m_partial[i].ssa_base;
776 if (base && name != base && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb)
777 {
778 relation_kind k = partial_equiv (ssa1: name, ssa2: base);
779 if (k != VREL_VARYING)
780 {
781 value_relation vr (k, name, base);
782 fprintf (stream: f, format: "Partial equiv ");
783 vr.dump (f);
784 fputc (c: '\n',stream: f);
785 }
786 }
787 }
788}
789
790// Dump all equivalence sets known to the oracle.
791
792void
793equiv_oracle::dump (FILE *f) const
794{
795 fprintf (stream: f, format: "Equivalency dump\n");
796 for (unsigned i = 0; i < m_equiv.length (); i++)
797 if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
798 {
799 fprintf (stream: f, format: "BB%d\n", i);
800 dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
801 }
802}
803
804
805// --------------------------------------------------------------------------
806// Negate the current relation.
807
808void
809value_relation::negate ()
810{
811 related = relation_negate (r: related);
812}
813
814// Perform an intersection between 2 relations. *this &&= p.
815
816bool
817value_relation::intersect (value_relation &p)
818{
819 // Save previous value
820 relation_kind old = related;
821
822 if (p.op1 () == op1 () && p.op2 () == op2 ())
823 related = relation_intersect (r1: kind (), r2: p.kind ());
824 else if (p.op2 () == op1 () && p.op1 () == op2 ())
825 related = relation_intersect (r1: kind (), r2: relation_swap (r: p.kind ()));
826 else
827 return false;
828
829 return old != related;
830}
831
832// Perform a union between 2 relations. *this ||= p.
833
834bool
835value_relation::union_ (value_relation &p)
836{
837 // Save previous value
838 relation_kind old = related;
839
840 if (p.op1 () == op1 () && p.op2 () == op2 ())
841 related = relation_union (r1: kind(), r2: p.kind());
842 else if (p.op2 () == op1 () && p.op1 () == op2 ())
843 related = relation_union (r1: kind(), r2: relation_swap (r: p.kind ()));
844 else
845 return false;
846
847 return old != related;
848}
849
850// Identify and apply any transitive relations between REL
851// and THIS. Return true if there was a transformation.
852
853bool
854value_relation::apply_transitive (const value_relation &rel)
855{
856 relation_kind k = VREL_VARYING;
857
858 // Identify any common operand, and normalize the relations to
859 // the form : A < B B < C produces A < C
860 if (rel.op1 () == name2)
861 {
862 // A < B B < C
863 if (rel.op2 () == name1)
864 return false;
865 k = relation_transitive (r1: kind (), r2: rel.kind ());
866 if (k != VREL_VARYING)
867 {
868 related = k;
869 name2 = rel.op2 ();
870 return true;
871 }
872 }
873 else if (rel.op1 () == name1)
874 {
875 // B > A B < C
876 if (rel.op2 () == name2)
877 return false;
878 k = relation_transitive (r1: relation_swap (r: kind ()), r2: rel.kind ());
879 if (k != VREL_VARYING)
880 {
881 related = k;
882 name1 = name2;
883 name2 = rel.op2 ();
884 return true;
885 }
886 }
887 else if (rel.op2 () == name2)
888 {
889 // A < B C > B
890 if (rel.op1 () == name1)
891 return false;
892 k = relation_transitive (r1: kind (), r2: relation_swap (r: rel.kind ()));
893 if (k != VREL_VARYING)
894 {
895 related = k;
896 name2 = rel.op1 ();
897 return true;
898 }
899 }
900 else if (rel.op2 () == name1)
901 {
902 // B > A C > B
903 if (rel.op1 () == name2)
904 return false;
905 k = relation_transitive (r1: relation_swap (r: kind ()),
906 r2: relation_swap (r: rel.kind ()));
907 if (k != VREL_VARYING)
908 {
909 related = k;
910 name1 = name2;
911 name2 = rel.op1 ();
912 return true;
913 }
914 }
915 return false;
916}
917
918// Create a trio from this value relation given LHS, OP1 and OP2.
919
920relation_trio
921value_relation::create_trio (tree lhs, tree op1, tree op2)
922{
923 relation_kind lhs_1;
924 if (lhs == name1 && op1 == name2)
925 lhs_1 = related;
926 else if (lhs == name2 && op1 == name1)
927 lhs_1 = relation_swap (r: related);
928 else
929 lhs_1 = VREL_VARYING;
930
931 relation_kind lhs_2;
932 if (lhs == name1 && op2 == name2)
933 lhs_2 = related;
934 else if (lhs == name2 && op2 == name1)
935 lhs_2 = relation_swap (r: related);
936 else
937 lhs_2 = VREL_VARYING;
938
939 relation_kind op_op;
940 if (op1 == name1 && op2 == name2)
941 op_op = related;
942 else if (op1 == name2 && op2 == name1)
943 op_op = relation_swap (r: related);
944 else if (op1 == op2)
945 op_op = VREL_EQ;
946 else
947 op_op = VREL_VARYING;
948
949 return relation_trio (lhs_1, lhs_2, op_op);
950}
951
952// Dump the relation to file F.
953
954void
955value_relation::dump (FILE *f) const
956{
957 if (!name1 || !name2)
958 {
959 fprintf (stream: f, format: "no relation registered");
960 return;
961 }
962 fputc (c: '(', stream: f);
963 print_generic_expr (f, op1 (), TDF_SLIM);
964 print_relation (f, rel: kind ());
965 print_generic_expr (f, op2 (), TDF_SLIM);
966 fputc(c: ')', stream: f);
967}
968
969// This container is used to link relations in a chain.
970
971class relation_chain : public value_relation
972{
973public:
974 relation_chain *m_next;
975};
976
977// ------------------------------------------------------------------------
978
979// Find the relation between any ssa_name in B1 and any name in B2 in LIST.
980// This will allow equivalencies to be applied to any SSA_NAME in a relation.
981
982relation_kind
983relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
984{
985 if (!m_names)
986 return VREL_VARYING;
987
988 // If both b1 and b2 aren't referenced in this block, cant be a relation
989 if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
990 return VREL_VARYING;
991
992 // Search for the first relation that contains BOTH an element from B1
993 // and B2, and return that relation.
994 for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
995 {
996 unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
997 unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
998 if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
999 return ptr->kind ();
1000 if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
1001 return relation_swap (r: ptr->kind ());
1002 }
1003
1004 return VREL_VARYING;
1005}
1006
1007// Instantiate a relation oracle.
1008
1009dom_oracle::dom_oracle ()
1010{
1011 m_relations.create (nelems: 0);
1012 m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1013 m_relation_set = BITMAP_ALLOC (obstack: &m_bitmaps);
1014 m_tmp = BITMAP_ALLOC (obstack: &m_bitmaps);
1015 m_tmp2 = BITMAP_ALLOC (obstack: &m_bitmaps);
1016}
1017
1018// Destruct a relation oracle.
1019
1020dom_oracle::~dom_oracle ()
1021{
1022 m_relations.release ();
1023}
1024
1025// Register relation K between ssa_name OP1 and OP2 on STMT.
1026
1027void
1028relation_oracle::register_stmt (gimple *stmt, relation_kind k, tree op1,
1029 tree op2)
1030{
1031 gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1032 gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1033 gcc_checking_assert (stmt && gimple_bb (stmt));
1034
1035 // Don't register lack of a relation.
1036 if (k == VREL_VARYING)
1037 return;
1038
1039 if (dump_file && (dump_flags & TDF_DETAILS))
1040 {
1041 value_relation vr (k, op1, op2);
1042 fprintf (stream: dump_file, format: " Registering value_relation ");
1043 vr.dump (f: dump_file);
1044 fprintf (stream: dump_file, format: " (bb%d) at ", gimple_bb (g: stmt)->index);
1045 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1046 }
1047
1048 // If an equivalence is being added between a PHI and one of its arguments
1049 // make sure that that argument is not defined in the same block.
1050 // This can happen along back edges and the equivalence will not be
1051 // applicable as it would require a use before def.
1052 if (k == VREL_EQ && is_a<gphi *> (p: stmt))
1053 {
1054 tree phi_def = gimple_phi_result (gs: stmt);
1055 gcc_checking_assert (phi_def == op1 || phi_def == op2);
1056 tree arg = op2;
1057 if (phi_def == op2)
1058 arg = op1;
1059 if (gimple_bb (g: stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
1060 {
1061 if (dump_file && (dump_flags & TDF_DETAILS))
1062 {
1063 fprintf (stream: dump_file, format: " Not registered due to ");
1064 print_generic_expr (dump_file, arg, TDF_SLIM);
1065 fprintf (stream: dump_file, format: " being defined in the same block.\n");
1066 }
1067 return;
1068 }
1069 }
1070 register_relation (gimple_bb (g: stmt), k, op1, op2);
1071}
1072
1073// Register relation K between ssa_name OP1 and OP2 on edge E.
1074
1075void
1076relation_oracle::register_edge (edge e, relation_kind k, tree op1, tree op2)
1077{
1078 gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1079 gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1080
1081 // Do not register lack of relation, or blocks which have more than
1082 // edge E for a predecessor.
1083 if (k == VREL_VARYING || !single_pred_p (bb: e->dest))
1084 return;
1085
1086 if (dump_file && (dump_flags & TDF_DETAILS))
1087 {
1088 value_relation vr (k, op1, op2);
1089 fprintf (stream: dump_file, format: " Registering value_relation ");
1090 vr.dump (f: dump_file);
1091 fprintf (stream: dump_file, format: " on (%d->%d)\n", e->src->index, e->dest->index);
1092 }
1093
1094 register_relation (e->dest, k, op1, op2);
1095}
1096
1097// Register relation K between OP! and OP2 in block BB.
1098// This creates the record and searches for existing records in the dominator
1099// tree to merge with.
1100
1101void
1102dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
1103 tree op2)
1104{
1105 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1106 // and no other relation makes sense.
1107 if (op1 == op2)
1108 return;
1109
1110 // Equivalencies are handled by the equivalence oracle.
1111 if (relation_equiv_p (r: k))
1112 equiv_oracle::register_relation (bb, k, ssa1: op1, ssa2: op2);
1113 else
1114 {
1115 // if neither op1 nor op2 are in a relation before this is registered,
1116 // there will be no transitive.
1117 bool check = bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op1))
1118 || bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op2));
1119 relation_chain *ptr = set_one_relation (bb, k, op1, op2);
1120 if (ptr && check)
1121 register_transitives (bb, *ptr);
1122 }
1123}
1124
1125// Register relation K between OP! and OP2 in block BB.
1126// This creates the record and searches for existing records in the dominator
1127// tree to merge with. Return the record, or NULL if no record was created.
1128
1129relation_chain *
1130dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1,
1131 tree op2)
1132{
1133 gcc_checking_assert (k != VREL_VARYING && k != VREL_EQ);
1134
1135 value_relation vr(k, op1, op2);
1136 int bbi = bb->index;
1137
1138 if (bbi >= (int)m_relations.length())
1139 m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1140
1141 // Summary bitmap indicating what ssa_names have relations in this BB.
1142 bitmap bm = m_relations[bbi].m_names;
1143 if (!bm)
1144 bm = m_relations[bbi].m_names = BITMAP_ALLOC (obstack: &m_bitmaps);
1145 unsigned v1 = SSA_NAME_VERSION (op1);
1146 unsigned v2 = SSA_NAME_VERSION (op2);
1147
1148 relation_kind curr;
1149 relation_chain *ptr;
1150 curr = find_relation_block (bb: bbi, v1, v2, obj: &ptr);
1151 // There is an existing relation in this block, just intersect with it.
1152 if (curr != VREL_VARYING)
1153 {
1154 if (dump_file && (dump_flags & TDF_DETAILS))
1155 {
1156 fprintf (stream: dump_file, format: " Intersecting with existing ");
1157 ptr->dump (f: dump_file);
1158 }
1159 // Check into whether we can simply replace the relation rather than
1160 // intersecting it. This may help with some optimistic iterative
1161 // updating algorithms.
1162 bool new_rel = ptr->intersect (p&: vr);
1163 if (dump_file && (dump_flags & TDF_DETAILS))
1164 {
1165 fprintf (stream: dump_file, format: " to produce ");
1166 ptr->dump (f: dump_file);
1167 fprintf (stream: dump_file, format: " %s.\n", new_rel ? "Updated" : "No Change");
1168 }
1169 // If there was no change, return no record..
1170 if (!new_rel)
1171 return NULL;
1172 }
1173 else
1174 {
1175 if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
1176 {
1177 if (dump_file && (dump_flags & TDF_DETAILS))
1178 fprintf (stream: dump_file, format: " Not registered due to bb being full\n");
1179 return NULL;
1180 }
1181 m_relations[bbi].m_num_relations++;
1182 // Check for an existing relation further up the DOM chain.
1183 // By including dominating relations, The first one found in any search
1184 // will be the aggregate of all the previous ones.
1185 curr = find_relation_dom (bb, v1, v2);
1186 if (curr != VREL_VARYING)
1187 k = relation_intersect (r1: curr, r2: k);
1188
1189 bitmap_set_bit (bm, v1);
1190 bitmap_set_bit (bm, v2);
1191 bitmap_set_bit (m_relation_set, v1);
1192 bitmap_set_bit (m_relation_set, v2);
1193
1194 ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1195 sizeof (relation_chain));
1196 ptr->set_relation (r: k, n1: op1, n2: op2);
1197 ptr->m_next = m_relations[bbi].m_head;
1198 m_relations[bbi].m_head = ptr;
1199 }
1200 return ptr;
1201}
1202
1203// Starting at ROOT_BB search the DOM tree looking for relations which
1204// may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
1205// bitmaps for op1/op2 and any of their equivalences that should also be
1206// considered.
1207
1208void
1209dom_oracle::register_transitives (basic_block root_bb,
1210 const value_relation &relation)
1211{
1212 basic_block bb;
1213 // Only apply transitives to certain kinds of operations.
1214 switch (relation.kind ())
1215 {
1216 case VREL_LE:
1217 case VREL_LT:
1218 case VREL_GT:
1219 case VREL_GE:
1220 break;
1221 default:
1222 return;
1223 }
1224
1225 const_bitmap equiv1 = equiv_set (ssa: relation.op1 (), bb: root_bb);
1226 const_bitmap equiv2 = equiv_set (ssa: relation.op2 (), bb: root_bb);
1227
1228 for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1229 {
1230 int bbi = bb->index;
1231 if (bbi >= (int)m_relations.length())
1232 continue;
1233 const_bitmap bm = m_relations[bbi].m_names;
1234 if (!bm)
1235 continue;
1236 if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
1237 continue;
1238 // At least one of the 2 ops has a relation in this block.
1239 relation_chain *ptr;
1240 for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
1241 {
1242 // In the presence of an equivalence, 2 operands may do not
1243 // naturally match. ie with equivalence a_2 == b_3
1244 // given c_1 < a_2 && b_3 < d_4
1245 // convert the second relation (b_3 < d_4) to match any
1246 // equivalences to found in the first relation.
1247 // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1248 // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1249
1250 tree r1, r2;
1251 tree p1 = ptr->op1 ();
1252 tree p2 = ptr->op2 ();
1253 // Find which equivalence is in the first operand.
1254 if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
1255 r1 = p1;
1256 else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
1257 r1 = p2;
1258 else
1259 r1 = NULL_TREE;
1260
1261 // Find which equivalence is in the second operand.
1262 if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
1263 r2 = p1;
1264 else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
1265 r2 = p2;
1266 else
1267 r2 = NULL_TREE;
1268
1269 // Ignore if both NULL (not relevant relation) or the same,
1270 if (r1 == r2)
1271 continue;
1272
1273 // Any operand not an equivalence, just take the real operand.
1274 if (!r1)
1275 r1 = relation.op1 ();
1276 if (!r2)
1277 r2 = relation.op2 ();
1278
1279 value_relation nr (relation.kind (), r1, r2);
1280 if (nr.apply_transitive (rel: *ptr))
1281 {
1282 if (!set_one_relation (bb: root_bb, k: nr.kind (), op1: nr.op1 (), op2: nr.op2 ()))
1283 return;
1284 if (dump_file && (dump_flags & TDF_DETAILS))
1285 {
1286 fprintf (stream: dump_file, format: " Registering transitive relation ");
1287 nr.dump (f: dump_file);
1288 fputc (c: '\n', stream: dump_file);
1289 }
1290 }
1291
1292 }
1293 }
1294}
1295
1296// Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1297// This will allow equivalencies to be applied to any SSA_NAME in a relation.
1298
1299relation_kind
1300dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
1301 const_bitmap b2) const
1302{
1303 if (bb >= m_relations.length())
1304 return VREL_VARYING;
1305
1306 return m_relations[bb].find_relation (b1, b2);
1307}
1308
1309// Search the DOM tree for a relation between an element of equivalency set B1
1310// and B2, starting with block BB.
1311
1312relation_kind
1313dom_oracle::query_relation (basic_block bb, const_bitmap b1,
1314 const_bitmap b2)
1315{
1316 relation_kind r;
1317 if (bitmap_equal_p (b1, b2))
1318 return VREL_EQ;
1319
1320 // If either name does not occur in a relation anywhere, there isn't one.
1321 if (!bitmap_intersect_p (m_relation_set, b1)
1322 || !bitmap_intersect_p (m_relation_set, b2))
1323 return VREL_VARYING;
1324
1325 // Search each block in the DOM tree checking.
1326 for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1327 {
1328 r = find_relation_block (bb: bb->index, b1, b2);
1329 if (r != VREL_VARYING)
1330 return r;
1331 }
1332 return VREL_VARYING;
1333
1334}
1335
1336// Find a relation in block BB between ssa version V1 and V2. If a relation
1337// is found, return a pointer to the chain object in OBJ.
1338
1339relation_kind
1340dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
1341 relation_chain **obj) const
1342{
1343 if (bb >= (int)m_relations.length())
1344 return VREL_VARYING;
1345
1346 const_bitmap bm = m_relations[bb].m_names;
1347 if (!bm)
1348 return VREL_VARYING;
1349
1350 // If both b1 and b2 aren't referenced in this block, cant be a relation
1351 if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1352 return VREL_VARYING;
1353
1354 relation_chain *ptr;
1355 for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1356 {
1357 unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1358 unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1359 if (v1 == op1 && v2 == op2)
1360 {
1361 if (obj)
1362 *obj = ptr;
1363 return ptr->kind ();
1364 }
1365 if (v1 == op2 && v2 == op1)
1366 {
1367 if (obj)
1368 *obj = ptr;
1369 return relation_swap (r: ptr->kind ());
1370 }
1371 }
1372
1373 return VREL_VARYING;
1374}
1375
1376// Find a relation between SSA version V1 and V2 in the dominator tree
1377// starting with block BB
1378
1379relation_kind
1380dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const
1381{
1382 relation_kind r;
1383 // IF either name does not occur in a relation anywhere, there isn't one.
1384 if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1385 return VREL_VARYING;
1386
1387 for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1388 {
1389 r = find_relation_block (bb: bb->index, v1, v2);
1390 if (r != VREL_VARYING)
1391 return r;
1392 }
1393 return VREL_VARYING;
1394
1395}
1396
1397// Query if there is a relation between SSA1 and SS2 in block BB or a
1398// dominator of BB
1399
1400relation_kind
1401dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1402{
1403 relation_kind kind;
1404 unsigned v1 = SSA_NAME_VERSION (ssa1);
1405 unsigned v2 = SSA_NAME_VERSION (ssa2);
1406 if (v1 == v2)
1407 return VREL_EQ;
1408
1409 // If v1 or v2 do not have any relations or equivalences, a partial
1410 // equivalence is the only possibility.
1411 if ((!bitmap_bit_p (m_relation_set, v1) && !has_equiv_p (v: v1))
1412 || (!bitmap_bit_p (m_relation_set, v2) && !has_equiv_p (v: v2)))
1413 return partial_equiv (ssa1, ssa2);
1414
1415 // Check for equivalence first. They must be in each equivalency set.
1416 const_bitmap equiv1 = equiv_set (ssa: ssa1, bb);
1417 const_bitmap equiv2 = equiv_set (ssa: ssa2, bb);
1418 if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
1419 return VREL_EQ;
1420
1421 kind = partial_equiv (ssa1, ssa2);
1422 if (kind != VREL_VARYING)
1423 return kind;
1424
1425 // Initially look for a direct relationship and just return that.
1426 kind = find_relation_dom (bb, v1, v2);
1427 if (kind != VREL_VARYING)
1428 return kind;
1429
1430 // Query using the equivalence sets.
1431 kind = query_relation (bb, b1: equiv1, b2: equiv2);
1432 return kind;
1433}
1434
1435// Dump all the relations in block BB to file F.
1436
1437void
1438dom_oracle::dump (FILE *f, basic_block bb) const
1439{
1440 equiv_oracle::dump (f,bb);
1441
1442 if (bb->index >= (int)m_relations.length ())
1443 return;
1444 if (!m_relations[bb->index].m_names)
1445 return;
1446
1447 relation_chain *ptr = m_relations[bb->index].m_head;
1448 for (; ptr; ptr = ptr->m_next)
1449 {
1450 fprintf (stream: f, format: "Relational : ");
1451 ptr->dump (f);
1452 fprintf (stream: f, format: "\n");
1453 }
1454}
1455
1456// Dump all the relations known to file F.
1457
1458void
1459dom_oracle::dump (FILE *f) const
1460{
1461 fprintf (stream: f, format: "Relation dump\n");
1462 for (unsigned i = 0; i < m_relations.length (); i++)
1463 if (BASIC_BLOCK_FOR_FN (cfun, i))
1464 {
1465 fprintf (stream: f, format: "BB%d\n", i);
1466 dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
1467 }
1468}
1469
1470void
1471relation_oracle::debug () const
1472{
1473 dump (stderr);
1474}
1475
1476path_oracle::path_oracle (relation_oracle *oracle)
1477{
1478 set_root_oracle (oracle);
1479 bitmap_obstack_initialize (&m_bitmaps);
1480 obstack_init (&m_chain_obstack);
1481
1482 // Initialize header records.
1483 m_equiv.m_names = BITMAP_ALLOC (obstack: &m_bitmaps);
1484 m_equiv.m_bb = NULL;
1485 m_equiv.m_next = NULL;
1486 m_relations.m_names = BITMAP_ALLOC (obstack: &m_bitmaps);
1487 m_relations.m_head = NULL;
1488 m_killed_defs = BITMAP_ALLOC (obstack: &m_bitmaps);
1489}
1490
1491path_oracle::~path_oracle ()
1492{
1493 obstack_free (&m_chain_obstack, NULL);
1494 bitmap_obstack_release (&m_bitmaps);
1495}
1496
1497// Return the equiv set for SSA, and if there isn't one, check for equivs
1498// starting in block BB.
1499
1500const_bitmap
1501path_oracle::equiv_set (tree ssa, basic_block bb)
1502{
1503 // Check the list first.
1504 equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
1505 if (ptr)
1506 return ptr->m_names;
1507
1508 // Otherwise defer to the root oracle.
1509 if (m_root)
1510 return m_root->equiv_set (ssa, bb);
1511
1512 // Allocate a throw away bitmap if there isn't a root oracle.
1513 bitmap tmp = BITMAP_ALLOC (obstack: &m_bitmaps);
1514 bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
1515 return tmp;
1516}
1517
1518// Register an equivalence between SSA1 and SSA2 resolving unknowns from
1519// block BB.
1520
1521void
1522path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
1523{
1524 const_bitmap equiv_1 = equiv_set (ssa: ssa1, bb);
1525 const_bitmap equiv_2 = equiv_set (ssa: ssa2, bb);
1526
1527 // Check if they are the same set, if so, we're done.
1528 if (bitmap_equal_p (equiv_1, equiv_2))
1529 return;
1530
1531 // Don't mess around, simply create a new record and insert it first.
1532 bitmap b = BITMAP_ALLOC (obstack: &m_bitmaps);
1533 valid_equivs (b, equivs: equiv_1, bb);
1534 valid_equivs (b, equivs: equiv_2, bb);
1535
1536 equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1537 sizeof (equiv_chain));
1538 ptr->m_names = b;
1539 ptr->m_bb = NULL;
1540 ptr->m_next = m_equiv.m_next;
1541 m_equiv.m_next = ptr;
1542 bitmap_ior_into (m_equiv.m_names, b);
1543}
1544
1545// Register killing definition of an SSA_NAME.
1546
1547void
1548path_oracle::killing_def (tree ssa)
1549{
1550 if (dump_file && (dump_flags & TDF_DETAILS))
1551 {
1552 fprintf (stream: dump_file, format: " Registering killing_def (path_oracle) ");
1553 print_generic_expr (dump_file, ssa, TDF_SLIM);
1554 fprintf (stream: dump_file, format: "\n");
1555 }
1556
1557 unsigned v = SSA_NAME_VERSION (ssa);
1558
1559 bitmap_set_bit (m_killed_defs, v);
1560 bitmap_set_bit (m_equiv.m_names, v);
1561
1562 // Now add an equivalency with itself so we don't look to the root oracle.
1563 bitmap b = BITMAP_ALLOC (obstack: &m_bitmaps);
1564 bitmap_set_bit (b, v);
1565 equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1566 sizeof (equiv_chain));
1567 ptr->m_names = b;
1568 ptr->m_bb = NULL;
1569 ptr->m_next = m_equiv.m_next;
1570 m_equiv.m_next = ptr;
1571
1572 // Walk the relation list and remove SSA from any relations.
1573 if (!bitmap_bit_p (m_relations.m_names, v))
1574 return;
1575
1576 bitmap_clear_bit (m_relations.m_names, v);
1577 relation_chain **prev = &(m_relations.m_head);
1578 relation_chain *next = NULL;
1579 for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
1580 {
1581 gcc_checking_assert (*prev == ptr);
1582 next = ptr->m_next;
1583 if (SSA_NAME_VERSION (ptr->op1 ()) == v
1584 || SSA_NAME_VERSION (ptr->op2 ()) == v)
1585 *prev = ptr->m_next;
1586 else
1587 prev = &(ptr->m_next);
1588 }
1589}
1590
1591// Register relation K between SSA1 and SSA2, resolving unknowns by
1592// querying from BB.
1593
1594void
1595path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
1596 tree ssa2)
1597{
1598 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1599 // and no other relation makes sense.
1600 if (ssa1 == ssa2)
1601 return;
1602
1603 if (dump_file && (dump_flags & TDF_DETAILS))
1604 {
1605 value_relation vr (k, ssa1, ssa2);
1606 fprintf (stream: dump_file, format: " Registering value_relation (path_oracle) ");
1607 vr.dump (f: dump_file);
1608 fprintf (stream: dump_file, format: " (root: bb%d)\n", bb->index);
1609 }
1610
1611 relation_kind curr = query_relation (bb, ssa1, ssa2);
1612 if (curr != VREL_VARYING)
1613 k = relation_intersect (r1: curr, r2: k);
1614
1615 if (k == VREL_EQ)
1616 {
1617 register_equiv (bb, ssa1, ssa2);
1618 return;
1619 }
1620
1621 bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
1622 bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
1623 relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1624 sizeof (relation_chain));
1625 ptr->set_relation (r: k, n1: ssa1, n2: ssa2);
1626 ptr->m_next = m_relations.m_head;
1627 m_relations.m_head = ptr;
1628}
1629
1630// Query for a relationship between equiv set B1 and B2, resolving unknowns
1631// starting at block BB.
1632
1633relation_kind
1634path_oracle::query_relation (basic_block bb, const_bitmap b1, const_bitmap b2)
1635{
1636 if (bitmap_equal_p (b1, b2))
1637 return VREL_EQ;
1638
1639 relation_kind k = m_relations.find_relation (b1, b2);
1640
1641 // Do not look at the root oracle for names that have been killed
1642 // along the path.
1643 if (bitmap_intersect_p (m_killed_defs, b1)
1644 || bitmap_intersect_p (m_killed_defs, b2))
1645 return k;
1646
1647 if (k == VREL_VARYING && m_root)
1648 k = m_root->query_relation (bb, b1, b2);
1649
1650 return k;
1651}
1652
1653// Query for a relationship between SSA1 and SSA2, resolving unknowns
1654// starting at block BB.
1655
1656relation_kind
1657path_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1658{
1659 unsigned v1 = SSA_NAME_VERSION (ssa1);
1660 unsigned v2 = SSA_NAME_VERSION (ssa2);
1661
1662 if (v1 == v2)
1663 return VREL_EQ;
1664
1665 const_bitmap equiv_1 = equiv_set (ssa: ssa1, bb);
1666 const_bitmap equiv_2 = equiv_set (ssa: ssa2, bb);
1667 if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
1668 return VREL_EQ;
1669
1670 return query_relation (bb, b1: equiv_1, b2: equiv_2);
1671}
1672
1673// Reset any relations registered on this path. ORACLE is the root
1674// oracle to use.
1675
1676void
1677path_oracle::reset_path (relation_oracle *oracle)
1678{
1679 set_root_oracle (oracle);
1680 m_equiv.m_next = NULL;
1681 bitmap_clear (m_equiv.m_names);
1682 m_relations.m_head = NULL;
1683 bitmap_clear (m_relations.m_names);
1684 bitmap_clear (m_killed_defs);
1685}
1686
1687// Dump relation in basic block... Do nothing here.
1688
1689void
1690path_oracle::dump (FILE *, basic_block) const
1691{
1692}
1693
1694// Dump the relations and equivalencies found in the path.
1695
1696void
1697path_oracle::dump (FILE *f) const
1698{
1699 equiv_chain *ptr = m_equiv.m_next;
1700 relation_chain *ptr2 = m_relations.m_head;
1701
1702 if (ptr || ptr2)
1703 fprintf (stream: f, format: "\npath_oracle:\n");
1704
1705 for (; ptr; ptr = ptr->m_next)
1706 ptr->dump (f);
1707
1708 for (; ptr2; ptr2 = ptr2->m_next)
1709 {
1710 fprintf (stream: f, format: "Relational : ");
1711 ptr2->dump (f);
1712 fprintf (stream: f, format: "\n");
1713 }
1714}
1715
1716// ------------------------------------------------------------------------
1717// EQUIV iterator. Although we have bitmap iterators, don't expose that it
1718// is currently a bitmap. Use an export iterator to hide future changes.
1719
1720// Construct a basic iterator over an equivalence bitmap.
1721
1722equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle,
1723 basic_block bb, tree name,
1724 bool full, bool partial)
1725{
1726 m_name = name;
1727 m_oracle = oracle;
1728 m_pe = partial ? oracle->partial_equiv_set (name) : NULL;
1729 m_bm = NULL;
1730 if (full)
1731 m_bm = oracle->equiv_set (name, bb);
1732 if (!m_bm && m_pe)
1733 m_bm = m_pe->members;
1734 if (m_bm)
1735 bmp_iter_set_init (bi: &m_bi, map: m_bm, start_bit: 1, bit_no: &m_y);
1736}
1737
1738// Move to the next export bitmap spot.
1739
1740void
1741equiv_relation_iterator::next ()
1742{
1743 bmp_iter_next (bi: &m_bi, bit_no: &m_y);
1744}
1745
1746// Fetch the name of the next export in the export list. Return NULL if
1747// iteration is done.
1748
1749tree
1750equiv_relation_iterator::get_name (relation_kind *rel)
1751{
1752 if (!m_bm)
1753 return NULL_TREE;
1754
1755 while (bmp_iter_set (bi: &m_bi, bit_no: &m_y))
1756 {
1757 // Do not return self.
1758 tree t = ssa_name (m_y);
1759 if (t && t != m_name)
1760 {
1761 relation_kind k = VREL_EQ;
1762 if (m_pe && m_bm == m_pe->members)
1763 {
1764 const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t);
1765 if (equiv_pe && equiv_pe->members == m_pe->members)
1766 k = pe_min (t1: m_pe->code, t2: equiv_pe->code);
1767 else
1768 k = VREL_VARYING;
1769 }
1770 if (relation_equiv_p (r: k))
1771 {
1772 if (rel)
1773 *rel = k;
1774 return t;
1775 }
1776 }
1777 next ();
1778 }
1779
1780 // Process partial equivs after full equivs if both were requested.
1781 if (m_pe && m_bm != m_pe->members)
1782 {
1783 m_bm = m_pe->members;
1784 if (m_bm)
1785 {
1786 // Recursively call back to process First PE.
1787 bmp_iter_set_init (bi: &m_bi, map: m_bm, start_bit: 1, bit_no: &m_y);
1788 return get_name (rel);
1789 }
1790 }
1791 return NULL_TREE;
1792}
1793
1794#if CHECKING_P
1795#include "selftest.h"
1796
1797namespace selftest
1798{
1799void
1800relation_tests ()
1801{
1802 // rr_*_table tables use unsigned char rather than relation_kind.
1803 ASSERT_LT (VREL_LAST, UCHAR_MAX);
1804 // Verify commutativity of relation_intersect and relation_union.
1805 for (relation_kind r1 = VREL_VARYING; r1 < VREL_PE8;
1806 r1 = relation_kind (r1 + 1))
1807 for (relation_kind r2 = VREL_VARYING; r2 < VREL_PE8;
1808 r2 = relation_kind (r2 + 1))
1809 {
1810 ASSERT_EQ (relation_intersect (r1, r2), relation_intersect (r2, r1));
1811 ASSERT_EQ (relation_union (r1, r2), relation_union (r2, r1));
1812 }
1813}
1814
1815} // namespace selftest
1816
1817#endif // CHECKING_P
1818

source code of gcc/value-relation.cc