compiler: only build thunk struct type when it is needed
[official-gcc.git] / gcc / value-relation.cc
blob1ee6da199f29b6e2f426219696f94b41b3be0807
1 /* Header file for the value range relational processing.
2 Copyright (C) 2020-2022 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
5 This file is part of GCC.
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.
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.
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/>. */
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"
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"
35 #define VREL_LAST VREL_NE
37 static const char *kind_string[VREL_LAST + 1] =
38 { "varying", "undefined", "<", "<=", ">", ">=", "==", "!=" };
40 // Print a relation_kind REL to file F.
42 void
43 print_relation (FILE *f, relation_kind rel)
45 fprintf (f, " %s ", kind_string[rel]);
48 // This table is used to negate the operands. op1 REL op2 -> !(op1 REL op2).
49 relation_kind rr_negate_table[VREL_LAST + 1] = {
50 VREL_VARYING, VREL_UNDEFINED, VREL_GE, VREL_GT, VREL_LE, VREL_LT, VREL_NE,
51 VREL_EQ };
53 // Negate the relation, as in logical negation.
55 relation_kind
56 relation_negate (relation_kind r)
58 return rr_negate_table [r];
61 // This table is used to swap the operands. op1 REL op2 -> op2 REL op1.
62 relation_kind rr_swap_table[VREL_LAST + 1] = {
63 VREL_VARYING, VREL_UNDEFINED, VREL_GT, VREL_GE, VREL_LT, VREL_LE, VREL_EQ,
64 VREL_NE };
66 // Return the relation as if the operands were swapped.
68 relation_kind
69 relation_swap (relation_kind r)
71 return rr_swap_table [r];
74 // This table is used to perform an intersection between 2 relations.
76 relation_kind rr_intersect_table[VREL_LAST + 1][VREL_LAST + 1] = {
77 // VREL_VARYING
78 { VREL_VARYING, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ,
79 VREL_NE },
80 // VREL_UNDEFINED
81 { VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED,
82 VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED },
83 // VREL_LT
84 { VREL_LT, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_UNDEFINED, VREL_UNDEFINED,
85 VREL_UNDEFINED, VREL_LT },
86 // VREL_LE
87 { VREL_LE, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_UNDEFINED, VREL_EQ,
88 VREL_EQ, VREL_LT },
89 // VREL_GT
90 { VREL_GT, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_GT, VREL_GT,
91 VREL_UNDEFINED, VREL_GT },
92 // VREL_GE
93 { VREL_GE, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_GT, VREL_GE,
94 VREL_EQ, VREL_GT },
95 // VREL_EQ
96 { VREL_EQ, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_UNDEFINED, VREL_EQ,
97 VREL_EQ, VREL_UNDEFINED },
98 // VREL_NE
99 { VREL_NE, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_GT, VREL_GT,
100 VREL_UNDEFINED, VREL_NE } };
103 // Intersect relation R1 with relation R2 and return the resulting relation.
105 relation_kind
106 relation_intersect (relation_kind r1, relation_kind r2)
108 return rr_intersect_table[r1][r2];
112 // This table is used to perform a union between 2 relations.
114 relation_kind rr_union_table[VREL_LAST + 1][VREL_LAST + 1] = {
115 // VREL_VARYING
116 { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
117 VREL_VARYING, VREL_VARYING, VREL_VARYING },
118 // VREL_UNDEFINED
119 { VREL_VARYING, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_UNDEFINED,
120 VREL_EQ, VREL_NE },
121 // VREL_LT
122 { VREL_VARYING, VREL_LT, VREL_LT, VREL_LE, VREL_NE, VREL_VARYING, VREL_LE,
123 VREL_NE },
124 // VREL_LE
125 { VREL_VARYING, VREL_LE, VREL_LE, VREL_LE, VREL_VARYING, VREL_VARYING,
126 VREL_LE, VREL_VARYING },
127 // VREL_GT
128 { VREL_VARYING, VREL_GT, VREL_NE, VREL_VARYING, VREL_GT, VREL_GE, VREL_GE,
129 VREL_NE },
130 // VREL_GE
131 { VREL_VARYING, VREL_GE, VREL_VARYING, VREL_VARYING, VREL_GE, VREL_GE,
132 VREL_GE, VREL_VARYING },
133 // VREL_EQ
134 { VREL_VARYING, VREL_EQ, VREL_LE, VREL_LE, VREL_GE, VREL_GE, VREL_EQ,
135 VREL_VARYING },
136 // VREL_NE
137 { VREL_VARYING, VREL_NE, VREL_NE, VREL_VARYING, VREL_NE, VREL_VARYING,
138 VREL_VARYING, VREL_NE } };
140 // Union relation R1 with relation R2 and return the result.
142 relation_kind
143 relation_union (relation_kind r1, relation_kind r2)
145 return rr_union_table[r1][r2];
149 // This table is used to determine transitivity between 2 relations.
150 // (A relation0 B) and (B relation1 C) implies (A result C)
152 relation_kind rr_transitive_table[VREL_LAST + 1][VREL_LAST + 1] = {
153 // VREL_VARYING
154 { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
155 VREL_VARYING, VREL_VARYING, VREL_VARYING },
156 // VREL_UNDEFINED
157 { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
158 VREL_VARYING, VREL_VARYING, VREL_VARYING },
159 // VREL_LT
160 { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LT, VREL_VARYING, VREL_VARYING,
161 VREL_LT, VREL_VARYING },
162 // VREL_LE
163 { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_VARYING, VREL_VARYING,
164 VREL_LE, VREL_VARYING },
165 // VREL_GT
166 { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GT,
167 VREL_GT, VREL_VARYING },
168 // VREL_GE
169 { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GE,
170 VREL_GE, VREL_VARYING },
171 // VREL_EQ
172 { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ,
173 VREL_VARYING },
174 // VREL_NE
175 { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
176 VREL_VARYING, VREL_VARYING, VREL_VARYING } };
178 // Apply transitive operation between relation R1 and relation R2, and
179 // return the resulting relation, if any.
181 relation_kind
182 relation_transitive (relation_kind r1, relation_kind r2)
184 return rr_transitive_table[r1][r2];
187 // This vector maps a relation to the equivalent tree code.
189 tree_code relation_to_code [VREL_LAST + 1] = {
190 ERROR_MARK, ERROR_MARK, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EQ_EXPR,
191 NE_EXPR };
193 // This routine validates that a relation can be applied to a specific set of
194 // ranges. In particular, floating point x == x may not be true if the NaN bit
195 // is set in the range. Symbolically the oracle will determine x == x,
196 // but specific range instances may override this.
197 // To verify, attempt to fold the relation using the supplied ranges.
198 // One would expect [1,1] to be returned, anything else means there is something
199 // in the range preventing the relation from applying.
200 // If there is no mechanism to verify, assume the relation is acceptable.
202 relation_kind
203 relation_oracle::validate_relation (relation_kind rel, vrange &op1, vrange &op2)
205 // If there is no mapping to a tree code, leave the relation as is.
206 tree_code code = relation_to_code [rel];
207 if (code == ERROR_MARK)
208 return rel;
210 // Undefined ranges cannot be checked either.
211 if (op1.undefined_p () || op2.undefined_p ())
212 return rel;
214 tree t1 = op1.type ();
215 tree t2 = op2.type ();
217 // If the range types are not compatible, no relation can exist.
218 if (!range_compatible_p (t1, t2))
219 return VREL_VARYING;
221 // If there is no handler, leave the relation as is.
222 range_op_handler handler (code, t1);
223 if (!handler)
224 return rel;
226 // If the relation cannot be folded for any reason, leave as is.
227 Value_Range result (boolean_type_node);
228 if (!handler.fold_range (result, boolean_type_node, op1, op2, rel))
229 return rel;
231 // The expression op1 REL op2 using REL should fold to [1,1].
232 // Any other result means the relation is not verified to be true.
233 if (result.varying_p () || result.zero_p ())
234 return VREL_VARYING;
236 return rel;
239 // If no range is available, create a varying range for each SSA name and
240 // verify.
242 relation_kind
243 relation_oracle::validate_relation (relation_kind rel, tree ssa1, tree ssa2)
245 Value_Range op1, op2;
246 op1.set_varying (TREE_TYPE (ssa1));
247 op2.set_varying (TREE_TYPE (ssa2));
249 return validate_relation (rel, op1, op2);
252 // Given an equivalence set EQUIV, set all the bits in B that are still valid
253 // members of EQUIV in basic block BB.
255 void
256 relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
258 unsigned i;
259 bitmap_iterator bi;
260 EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
262 tree ssa = ssa_name (i);
263 const_bitmap ssa_equiv = equiv_set (ssa, bb);
264 if (ssa_equiv == equivs)
265 bitmap_set_bit (b, i);
269 // -------------------------------------------------------------------------
271 // The very first element in the m_equiv chain is actually just a summary
272 // element in which the m_names bitmap is used to indicate that an ssa_name
273 // has an equivalence set in this block.
274 // This allows for much faster traversal of the DOM chain, as a search for
275 // SSA_NAME simply requires walking the DOM chain until a block is found
276 // which has the bit for SSA_NAME set. Then scan for the equivalency set in
277 // that block. No previous lists need be searched.
279 // If SSA has an equivalence in this list, find and return it.
280 // Otherwise return NULL.
282 equiv_chain *
283 equiv_chain::find (unsigned ssa)
285 equiv_chain *ptr = NULL;
286 // If there are equiv sets and SSA is in one in this list, find it.
287 // Otherwise return NULL.
288 if (bitmap_bit_p (m_names, ssa))
290 for (ptr = m_next; ptr; ptr = ptr->m_next)
291 if (bitmap_bit_p (ptr->m_names, ssa))
292 break;
294 return ptr;
297 // Dump the names in this equivalence set.
299 void
300 equiv_chain::dump (FILE *f) const
302 bitmap_iterator bi;
303 unsigned i;
305 if (!m_names)
306 return;
307 fprintf (f, "Equivalence set : [");
308 unsigned c = 0;
309 EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
311 if (ssa_name (i))
313 if (c++)
314 fprintf (f, ", ");
315 print_generic_expr (f, ssa_name (i), TDF_SLIM);
318 fprintf (f, "]\n");
321 // Instantiate an equivalency oracle.
323 equiv_oracle::equiv_oracle ()
325 bitmap_obstack_initialize (&m_bitmaps);
326 m_equiv.create (0);
327 m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
328 m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
329 obstack_init (&m_chain_obstack);
330 m_self_equiv.create (0);
331 m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
334 // Destruct an equivalency oracle.
336 equiv_oracle::~equiv_oracle ()
338 m_self_equiv.release ();
339 obstack_free (&m_chain_obstack, NULL);
340 m_equiv.release ();
341 bitmap_obstack_release (&m_bitmaps);
344 // Find and return the equivalency set for SSA along the dominators of BB.
345 // This is the external API.
347 const_bitmap
348 equiv_oracle::equiv_set (tree ssa, basic_block bb)
350 // Search the dominator tree for an equivalency.
351 equiv_chain *equiv = find_equiv_dom (ssa, bb);
352 if (equiv)
353 return equiv->m_names;
355 // Otherwise return a cached equiv set containing just this SSA.
356 unsigned v = SSA_NAME_VERSION (ssa);
357 if (v >= m_self_equiv.length ())
358 m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
360 if (!m_self_equiv[v])
362 m_self_equiv[v] = BITMAP_ALLOC (&m_bitmaps);
363 bitmap_set_bit (m_self_equiv[v], v);
365 return m_self_equiv[v];
368 // Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
370 relation_kind
371 equiv_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
373 // If the 2 ssa names share the same equiv set, they are equal.
374 if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb))
375 return VREL_EQ;
376 return VREL_VARYING;
379 // Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
381 relation_kind
382 equiv_oracle::query_relation (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1,
383 const_bitmap e2)
385 // If the 2 ssa names share the same equiv set, they are equal.
386 if (bitmap_equal_p (e1, e2))
387 return VREL_EQ;
388 return VREL_VARYING;
391 // If SSA has an equivalence in block BB, find and return it.
392 // Otherwise return NULL.
394 equiv_chain *
395 equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
397 if (bb >= (int)m_equiv.length () || !m_equiv[bb])
398 return NULL;
400 return m_equiv[bb]->find (ssa);
403 // Starting at block BB, walk the dominator chain looking for the nearest
404 // equivalence set containing NAME.
406 equiv_chain *
407 equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
409 unsigned v = SSA_NAME_VERSION (name);
410 // Short circuit looking for names which have no equivalences.
411 // Saves time looking for something which does not exist.
412 if (!bitmap_bit_p (m_equiv_set, v))
413 return NULL;
415 // NAME has at least once equivalence set, check to see if it has one along
416 // the dominator tree.
417 for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
419 equiv_chain *ptr = find_equiv_block (v, bb->index);
420 if (ptr)
421 return ptr;
423 return NULL;
426 // Register equivalance between ssa_name V and set EQUIV in block BB,
428 bitmap
429 equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
431 // V will have an equivalency now.
432 bitmap_set_bit (m_equiv_set, v);
434 // If that equiv chain is in this block, simply use it.
435 if (equiv->m_bb == bb)
437 bitmap_set_bit (equiv->m_names, v);
438 bitmap_set_bit (m_equiv[bb->index]->m_names, v);
439 return NULL;
442 // Otherwise create an equivalence for this block which is a copy
443 // of equiv, the add V to the set.
444 bitmap b = BITMAP_ALLOC (&m_bitmaps);
445 valid_equivs (b, equiv->m_names, bb);
446 bitmap_set_bit (b, v);
447 return b;
450 // Register equivalence between set equiv_1 and equiv_2 in block BB.
451 // Return NULL if either name can be merged with the other. Otherwise
452 // return a pointer to the combined bitmap of names. This allows the
453 // caller to do any setup required for a new element.
455 bitmap
456 equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
457 equiv_chain *equiv_2)
459 // If equiv_1 is already in BB, use it as the combined set.
460 if (equiv_1->m_bb == bb)
462 valid_equivs (equiv_1->m_names, equiv_2->m_names, bb);
463 // Its hard to delete from a single linked list, so
464 // just clear the second one.
465 if (equiv_2->m_bb == bb)
466 bitmap_clear (equiv_2->m_names);
467 else
468 // Ensure the new names are in the summary for BB.
469 bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
470 return NULL;
472 // If equiv_2 is in BB, use it for the combined set.
473 if (equiv_2->m_bb == bb)
475 valid_equivs (equiv_2->m_names, equiv_1->m_names, bb);
476 // Ensure the new names are in the summary.
477 bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
478 return NULL;
481 // At this point, neither equivalence is from this block.
482 bitmap b = BITMAP_ALLOC (&m_bitmaps);
483 valid_equivs (b, equiv_1->m_names, bb);
484 valid_equivs (b, equiv_2->m_names, bb);
485 return b;
488 // Create an equivalency set containing only SSA in its definition block.
489 // This is done the first time SSA is registered in an equivalency and blocks
490 // any DOM searches past the definition.
492 void
493 equiv_oracle::register_initial_def (tree ssa)
495 if (SSA_NAME_IS_DEFAULT_DEF (ssa))
496 return;
497 basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
498 gcc_checking_assert (bb && !find_equiv_dom (ssa, bb));
500 unsigned v = SSA_NAME_VERSION (ssa);
501 bitmap_set_bit (m_equiv_set, v);
502 bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps);
503 bitmap_set_bit (equiv_set, v);
504 add_equiv_to_block (bb, equiv_set);
507 // Register an equivalence between SSA1 and SSA2 in block BB.
508 // The equivalence oracle maintains a vector of equivalencies indexed by basic
509 // block. When an equivalence bteween SSA1 and SSA2 is registered in block BB,
510 // a query is made as to what equivalences both names have already, and
511 // any preexisting equivalences are merged to create a single equivalence
512 // containing all the ssa_names in this basic block.
514 void
515 equiv_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
516 tree ssa2)
518 // Only handle equality relations.
519 if (k != VREL_EQ)
520 return;
522 unsigned v1 = SSA_NAME_VERSION (ssa1);
523 unsigned v2 = SSA_NAME_VERSION (ssa2);
525 // If this is the first time an ssa_name has an equivalency registered
526 // create a self-equivalency record in the def block.
527 if (!bitmap_bit_p (m_equiv_set, v1))
528 register_initial_def (ssa1);
529 if (!bitmap_bit_p (m_equiv_set, v2))
530 register_initial_def (ssa2);
532 equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
533 equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
535 // Check if they are the same set
536 if (equiv_1 && equiv_1 == equiv_2)
537 return;
539 bitmap equiv_set;
541 // Case where we have 2 SSA_NAMEs that are not in any set.
542 if (!equiv_1 && !equiv_2)
544 bitmap_set_bit (m_equiv_set, v1);
545 bitmap_set_bit (m_equiv_set, v2);
547 equiv_set = BITMAP_ALLOC (&m_bitmaps);
548 bitmap_set_bit (equiv_set, v1);
549 bitmap_set_bit (equiv_set, v2);
551 else if (!equiv_1 && equiv_2)
552 equiv_set = register_equiv (bb, v1, equiv_2);
553 else if (equiv_1 && !equiv_2)
554 equiv_set = register_equiv (bb, v2, equiv_1);
555 else
556 equiv_set = register_equiv (bb, equiv_1, equiv_2);
558 // A non-null return is a bitmap that is to be added to the current
559 // block as a new equivalence.
560 if (!equiv_set)
561 return;
563 add_equiv_to_block (bb, equiv_set);
566 // Add an equivalency record in block BB containing bitmap EQUIV_SET.
567 // Note the internal caller is responible for allocating EQUIV_SET properly.
569 void
570 equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
572 equiv_chain *ptr;
574 // Check if this is the first time a block has an equivalence added.
575 // and create a header block. And set the summary for this block.
576 if (!m_equiv[bb->index])
578 ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
579 sizeof (equiv_chain));
580 ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
581 bitmap_copy (ptr->m_names, equiv_set);
582 ptr->m_bb = bb;
583 ptr->m_next = NULL;
584 m_equiv[bb->index] = ptr;
587 // Now create the element for this equiv set and initialize it.
588 ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
589 ptr->m_names = equiv_set;
590 ptr->m_bb = bb;
591 gcc_checking_assert (bb->index < (int)m_equiv.length ());
592 ptr->m_next = m_equiv[bb->index]->m_next;
593 m_equiv[bb->index]->m_next = ptr;
594 bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
597 // Make sure the BB vector is big enough and grow it if needed.
599 void
600 equiv_oracle::limit_check (basic_block bb)
602 int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
603 if (i >= (int)m_equiv.length ())
604 m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
607 // Dump the equivalence sets in BB to file F.
609 void
610 equiv_oracle::dump (FILE *f, basic_block bb) const
612 if (bb->index >= (int)m_equiv.length ())
613 return;
614 if (!m_equiv[bb->index])
615 return;
617 equiv_chain *ptr = m_equiv[bb->index]->m_next;
618 for (; ptr; ptr = ptr->m_next)
619 ptr->dump (f);
622 // Dump all equivalence sets known to the oracle.
624 void
625 equiv_oracle::dump (FILE *f) const
627 fprintf (f, "Equivalency dump\n");
628 for (unsigned i = 0; i < m_equiv.length (); i++)
629 if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
631 fprintf (f, "BB%d\n", i);
632 dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
637 // --------------------------------------------------------------------------
638 // Negate the current relation.
640 void
641 value_relation::negate ()
643 related = relation_negate (related);
646 // Perform an intersection between 2 relations. *this &&= p.
648 bool
649 value_relation::intersect (value_relation &p)
651 // Save previous value
652 relation_kind old = related;
654 if (p.op1 () == op1 () && p.op2 () == op2 ())
655 related = relation_intersect (kind (), p.kind ());
656 else if (p.op2 () == op1 () && p.op1 () == op2 ())
657 related = relation_intersect (kind (), relation_swap (p.kind ()));
658 else
659 return false;
661 return old != related;
664 // Perform a union between 2 relations. *this ||= p.
666 bool
667 value_relation::union_ (value_relation &p)
669 // Save previous value
670 relation_kind old = related;
672 if (p.op1 () == op1 () && p.op2 () == op2 ())
673 related = relation_union (kind(), p.kind());
674 else if (p.op2 () == op1 () && p.op1 () == op2 ())
675 related = relation_union (kind(), relation_swap (p.kind ()));
676 else
677 return false;
679 return old != related;
682 // Identify and apply any transitive relations between REL
683 // and THIS. Return true if there was a transformation.
685 bool
686 value_relation::apply_transitive (const value_relation &rel)
688 relation_kind k = VREL_VARYING;
690 // Idenity any common operand, and notrmalize the relations to
691 // the form : A < B B < C produces A < C
692 if (rel.op1 () == name2)
694 // A < B B < C
695 if (rel.op2 () == name1)
696 return false;
697 k = relation_transitive (kind (), rel.kind ());
698 if (k != VREL_VARYING)
700 related = k;
701 name2 = rel.op2 ();
702 return true;
705 else if (rel.op1 () == name1)
707 // B > A B < C
708 if (rel.op2 () == name2)
709 return false;
710 k = relation_transitive (relation_swap (kind ()), rel.kind ());
711 if (k != VREL_VARYING)
713 related = k;
714 name1 = name2;
715 name2 = rel.op2 ();
716 return true;
719 else if (rel.op2 () == name2)
721 // A < B C > B
722 if (rel.op1 () == name1)
723 return false;
724 k = relation_transitive (kind (), relation_swap (rel.kind ()));
725 if (k != VREL_VARYING)
727 related = k;
728 name2 = rel.op1 ();
729 return true;
732 else if (rel.op2 () == name1)
734 // B > A C > B
735 if (rel.op1 () == name2)
736 return false;
737 k = relation_transitive (relation_swap (kind ()),
738 relation_swap (rel.kind ()));
739 if (k != VREL_VARYING)
741 related = k;
742 name1 = name2;
743 name2 = rel.op1 ();
744 return true;
747 return false;
750 // Dump the relation to file F.
752 void
753 value_relation::dump (FILE *f) const
755 if (!name1 || !name2)
757 fprintf (f, "uninitialized");
758 return;
760 fputc ('(', f);
761 print_generic_expr (f, op1 (), TDF_SLIM);
762 print_relation (f, kind ());
763 print_generic_expr (f, op2 (), TDF_SLIM);
764 fputc(')', f);
767 // This container is used to link relations in a chain.
769 class relation_chain : public value_relation
771 public:
772 relation_chain *m_next;
775 // ------------------------------------------------------------------------
777 // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
778 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
780 relation_kind
781 relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
783 if (!m_names)
784 return VREL_VARYING;
786 // If both b1 and b2 aren't referenced in thie block, cant be a relation
787 if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
788 return VREL_VARYING;
790 // Search for the fiorst relation that contains BOTH an element from B1
791 // and B2, and return that relation.
792 for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
794 unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
795 unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
796 if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
797 return ptr->kind ();
798 if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
799 return relation_swap (ptr->kind ());
802 return VREL_VARYING;
805 // Instantiate a relation oracle.
807 dom_oracle::dom_oracle ()
809 m_relations.create (0);
810 m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
811 m_relation_set = BITMAP_ALLOC (&m_bitmaps);
812 m_tmp = BITMAP_ALLOC (&m_bitmaps);
813 m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
816 // Destruct a relation oracle.
818 dom_oracle::~dom_oracle ()
820 m_relations.release ();
823 // Register relation K between ssa_name OP1 and OP2 on STMT.
825 void
826 relation_oracle::register_stmt (gimple *stmt, relation_kind k, tree op1,
827 tree op2)
829 gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
830 gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
831 gcc_checking_assert (stmt && gimple_bb (stmt));
833 // Don't register lack of a relation.
834 if (k == VREL_VARYING)
835 return;
837 if (dump_file && (dump_flags & TDF_DETAILS))
839 value_relation vr (k, op1, op2);
840 fprintf (dump_file, " Registering value_relation ");
841 vr.dump (dump_file);
842 fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
843 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
846 // If an equivalence is being added between a PHI and one of its arguments
847 // make sure that that argument is not defined in the same block.
848 // This can happen along back edges and the equivalence will not be
849 // applicable as it would require a use before def.
850 if (k == VREL_EQ && is_a<gphi *> (stmt))
852 tree phi_def = gimple_phi_result (stmt);
853 gcc_checking_assert (phi_def == op1 || phi_def == op2);
854 tree arg = op2;
855 if (phi_def == op2)
856 arg = op1;
857 if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
859 if (dump_file && (dump_flags & TDF_DETAILS))
861 fprintf (dump_file, " Not registered due to ");
862 print_generic_expr (dump_file, arg, TDF_SLIM);
863 fprintf (dump_file, " being defined in the same block.\n");
865 return;
868 register_relation (gimple_bb (stmt), k, op1, op2);
871 // Register relation K between ssa_name OP1 and OP2 on edge E.
873 void
874 relation_oracle::register_edge (edge e, relation_kind k, tree op1, tree op2)
876 gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
877 gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
879 // Do not register lack of relation, or blocks which have more than
880 // edge E for a predecessor.
881 if (k == VREL_VARYING || !single_pred_p (e->dest))
882 return;
884 if (dump_file && (dump_flags & TDF_DETAILS))
886 value_relation vr (k, op1, op2);
887 fprintf (dump_file, " Registering value_relation ");
888 vr.dump (dump_file);
889 fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
892 register_relation (e->dest, k, op1, op2);
895 // Register relation K between OP! and OP2 in block BB.
896 // This creates the record and searches for existing records in the dominator
897 // tree to merge with.
899 void
900 dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
901 tree op2)
903 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
904 // and no other relation makes sense.
905 if (op1 == op2)
906 return;
908 // Equivalencies are handled by the equivalence oracle.
909 if (k == VREL_EQ)
910 equiv_oracle::register_relation (bb, k, op1, op2);
911 else
913 // if neither op1 nor op2 are in a relation before this is registered,
914 // there will be no transitive.
915 bool check = bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op1))
916 || bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op2));
917 relation_chain *ptr = set_one_relation (bb, k, op1, op2);
918 if (ptr && check)
919 register_transitives (bb, *ptr);
923 // Register relation K between OP! and OP2 in block BB.
924 // This creates the record and searches for existing records in the dominator
925 // tree to merge with. Return the record, or NULL if no record was created.
927 relation_chain *
928 dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1,
929 tree op2)
931 gcc_checking_assert (k != VREL_VARYING && k != VREL_EQ);
933 value_relation vr(k, op1, op2);
934 int bbi = bb->index;
936 if (bbi >= (int)m_relations.length())
937 m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
939 // Summary bitmap indicating what ssa_names have relations in this BB.
940 bitmap bm = m_relations[bbi].m_names;
941 if (!bm)
942 bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
943 unsigned v1 = SSA_NAME_VERSION (op1);
944 unsigned v2 = SSA_NAME_VERSION (op2);
946 relation_kind curr;
947 relation_chain *ptr;
948 curr = find_relation_block (bbi, v1, v2, &ptr);
949 // There is an existing relation in this block, just intersect with it.
950 if (curr != VREL_VARYING)
952 if (dump_file && (dump_flags & TDF_DETAILS))
954 fprintf (dump_file, " Intersecting with existing ");
955 ptr->dump (dump_file);
957 // Check into whether we can simply replace the relation rather than
958 // intersecting it. This may help with some optimistic iterative
959 // updating algorithms.
960 bool new_rel = ptr->intersect (vr);
961 if (dump_file && (dump_flags & TDF_DETAILS))
963 fprintf (dump_file, " to produce ");
964 ptr->dump (dump_file);
965 fprintf (dump_file, " %s.\n", new_rel ? "Updated" : "No Change");
967 // If there was no change, return no record..
968 if (!new_rel)
969 return NULL;
971 else
973 if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
975 if (dump_file && (dump_flags & TDF_DETAILS))
976 fprintf (dump_file, " Not registered due to bb being full\n");
977 return NULL;
979 m_relations[bbi].m_num_relations++;
980 // Check for an existing relation further up the DOM chain.
981 // By including dominating relations, The first one found in any search
982 // will be the aggregate of all the previous ones.
983 curr = find_relation_dom (bb, v1, v2);
984 if (curr != VREL_VARYING)
985 k = relation_intersect (curr, k);
987 bitmap_set_bit (bm, v1);
988 bitmap_set_bit (bm, v2);
989 bitmap_set_bit (m_relation_set, v1);
990 bitmap_set_bit (m_relation_set, v2);
992 ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
993 sizeof (relation_chain));
994 ptr->set_relation (k, op1, op2);
995 ptr->m_next = m_relations[bbi].m_head;
996 m_relations[bbi].m_head = ptr;
998 return ptr;
1001 // Starting at ROOT_BB search the DOM tree looking for relations which
1002 // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
1003 // bitmaps for op1/op2 and any of their equivalences that should also be
1004 // considered.
1006 void
1007 dom_oracle::register_transitives (basic_block root_bb,
1008 const value_relation &relation)
1010 basic_block bb;
1011 // Only apply transitives to certain kinds of operations.
1012 switch (relation.kind ())
1014 case VREL_LE:
1015 case VREL_LT:
1016 case VREL_GT:
1017 case VREL_GE:
1018 break;
1019 default:
1020 return;
1023 const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb);
1024 const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb);
1026 for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1028 int bbi = bb->index;
1029 if (bbi >= (int)m_relations.length())
1030 continue;
1031 const_bitmap bm = m_relations[bbi].m_names;
1032 if (!bm)
1033 continue;
1034 if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
1035 continue;
1036 // At least one of the 2 ops has a relation in this block.
1037 relation_chain *ptr;
1038 for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
1040 // In the presence of an equivalence, 2 operands may do not
1041 // naturally match. ie with equivalence a_2 == b_3
1042 // given c_1 < a_2 && b_3 < d_4
1043 // convert the second relation (b_3 < d_4) to match any
1044 // equivalences to found in the first relation.
1045 // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1046 // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1048 tree r1, r2;
1049 tree p1 = ptr->op1 ();
1050 tree p2 = ptr->op2 ();
1051 // Find which equivalence is in the first operand.
1052 if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
1053 r1 = p1;
1054 else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
1055 r1 = p2;
1056 else
1057 r1 = NULL_TREE;
1059 // Find which equivalence is in the second operand.
1060 if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
1061 r2 = p1;
1062 else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
1063 r2 = p2;
1064 else
1065 r2 = NULL_TREE;
1067 // Ignore if both NULL (not relevant relation) or the same,
1068 if (r1 == r2)
1069 continue;
1071 // Any operand not an equivalence, just take the real operand.
1072 if (!r1)
1073 r1 = relation.op1 ();
1074 if (!r2)
1075 r2 = relation.op2 ();
1077 value_relation nr (relation.kind (), r1, r2);
1078 if (nr.apply_transitive (*ptr))
1080 if (!set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ()))
1081 return;
1082 if (dump_file && (dump_flags & TDF_DETAILS))
1084 fprintf (dump_file, " Registering transitive relation ");
1085 nr.dump (dump_file);
1086 fputc ('\n', dump_file);
1094 // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1095 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1097 relation_kind
1098 dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
1099 const_bitmap b2) const
1101 if (bb >= m_relations.length())
1102 return VREL_VARYING;
1104 return m_relations[bb].find_relation (b1, b2);
1107 // Search the DOM tree for a relation between an element of equivalency set B1
1108 // and B2, starting with block BB.
1110 relation_kind
1111 dom_oracle::query_relation (basic_block bb, const_bitmap b1,
1112 const_bitmap b2)
1114 relation_kind r;
1115 if (bitmap_equal_p (b1, b2))
1116 return VREL_EQ;
1118 // If either name does not occur in a relation anywhere, there isnt one.
1119 if (!bitmap_intersect_p (m_relation_set, b1)
1120 || !bitmap_intersect_p (m_relation_set, b2))
1121 return VREL_VARYING;
1123 // Search each block in the DOM tree checking.
1124 for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1126 r = find_relation_block (bb->index, b1, b2);
1127 if (r != VREL_VARYING)
1128 return r;
1130 return VREL_VARYING;
1134 // Find a relation in block BB between ssa version V1 and V2. If a relation
1135 // is found, return a pointer to the chain object in OBJ.
1137 relation_kind
1138 dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
1139 relation_chain **obj) const
1141 if (bb >= (int)m_relations.length())
1142 return VREL_VARYING;
1144 const_bitmap bm = m_relations[bb].m_names;
1145 if (!bm)
1146 return VREL_VARYING;
1148 // If both b1 and b2 aren't referenced in thie block, cant be a relation
1149 if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1150 return VREL_VARYING;
1152 relation_chain *ptr;
1153 for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1155 unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1156 unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1157 if (v1 == op1 && v2 == op2)
1159 if (obj)
1160 *obj = ptr;
1161 return ptr->kind ();
1163 if (v1 == op2 && v2 == op1)
1165 if (obj)
1166 *obj = ptr;
1167 return relation_swap (ptr->kind ());
1171 return VREL_VARYING;
1174 // Find a relation between SSA version V1 and V2 in the dominator tree
1175 // starting with block BB
1177 relation_kind
1178 dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const
1180 relation_kind r;
1181 // IF either name does not occur in a relation anywhere, there isnt one.
1182 if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1183 return VREL_VARYING;
1185 for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1187 r = find_relation_block (bb->index, v1, v2);
1188 if (r != VREL_VARYING)
1189 return r;
1191 return VREL_VARYING;
1195 // Query if there is a relation between SSA1 and SS2 in block BB or a
1196 // dominator of BB
1198 relation_kind
1199 dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1201 relation_kind kind;
1202 unsigned v1 = SSA_NAME_VERSION (ssa1);
1203 unsigned v2 = SSA_NAME_VERSION (ssa2);
1204 if (v1 == v2)
1205 return VREL_EQ;
1207 // Check for equivalence first. They must be in each equivalency set.
1208 const_bitmap equiv1 = equiv_set (ssa1, bb);
1209 const_bitmap equiv2 = equiv_set (ssa2, bb);
1210 if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
1211 return VREL_EQ;
1213 // Initially look for a direct relationship and just return that.
1214 kind = find_relation_dom (bb, v1, v2);
1215 if (kind != VREL_VARYING)
1216 return kind;
1218 // Query using the equivalence sets.
1219 kind = query_relation (bb, equiv1, equiv2);
1220 return kind;
1223 // Dump all the relations in block BB to file F.
1225 void
1226 dom_oracle::dump (FILE *f, basic_block bb) const
1228 equiv_oracle::dump (f,bb);
1230 if (bb->index >= (int)m_relations.length ())
1231 return;
1232 if (!m_relations[bb->index].m_names)
1233 return;
1235 relation_chain *ptr = m_relations[bb->index].m_head;
1236 for (; ptr; ptr = ptr->m_next)
1238 fprintf (f, "Relational : ");
1239 ptr->dump (f);
1240 fprintf (f, "\n");
1244 // Dump all the relations known to file F.
1246 void
1247 dom_oracle::dump (FILE *f) const
1249 fprintf (f, "Relation dump\n");
1250 for (unsigned i = 0; i < m_relations.length (); i++)
1251 if (BASIC_BLOCK_FOR_FN (cfun, i))
1253 fprintf (f, "BB%d\n", i);
1254 dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
1258 void
1259 relation_oracle::debug () const
1261 dump (stderr);
1264 path_oracle::path_oracle (relation_oracle *oracle)
1266 set_root_oracle (oracle);
1267 bitmap_obstack_initialize (&m_bitmaps);
1268 obstack_init (&m_chain_obstack);
1270 // Initialize header records.
1271 m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
1272 m_equiv.m_bb = NULL;
1273 m_equiv.m_next = NULL;
1274 m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
1275 m_relations.m_head = NULL;
1276 m_killed_defs = BITMAP_ALLOC (&m_bitmaps);
1279 path_oracle::~path_oracle ()
1281 obstack_free (&m_chain_obstack, NULL);
1282 bitmap_obstack_release (&m_bitmaps);
1285 // Return the equiv set for SSA, and if there isn't one, check for equivs
1286 // starting in block BB.
1288 const_bitmap
1289 path_oracle::equiv_set (tree ssa, basic_block bb)
1291 // Check the list first.
1292 equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
1293 if (ptr)
1294 return ptr->m_names;
1296 // Otherwise defer to the root oracle.
1297 if (m_root)
1298 return m_root->equiv_set (ssa, bb);
1300 // Allocate a throw away bitmap if there isn't a root oracle.
1301 bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
1302 bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
1303 return tmp;
1306 // Register an equivalence between SSA1 and SSA2 resolving unkowns from
1307 // block BB.
1309 void
1310 path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
1312 const_bitmap equiv_1 = equiv_set (ssa1, bb);
1313 const_bitmap equiv_2 = equiv_set (ssa2, bb);
1315 // Check if they are the same set, if so, we're done.
1316 if (bitmap_equal_p (equiv_1, equiv_2))
1317 return;
1319 // Don't mess around, simply create a new record and insert it first.
1320 bitmap b = BITMAP_ALLOC (&m_bitmaps);
1321 valid_equivs (b, equiv_1, bb);
1322 valid_equivs (b, equiv_2, bb);
1324 equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1325 sizeof (equiv_chain));
1326 ptr->m_names = b;
1327 ptr->m_bb = NULL;
1328 ptr->m_next = m_equiv.m_next;
1329 m_equiv.m_next = ptr;
1330 bitmap_ior_into (m_equiv.m_names, b);
1333 // Register killing definition of an SSA_NAME.
1335 void
1336 path_oracle::killing_def (tree ssa)
1338 if (dump_file && (dump_flags & TDF_DETAILS))
1340 fprintf (dump_file, " Registering killing_def (path_oracle) ");
1341 print_generic_expr (dump_file, ssa, TDF_SLIM);
1342 fprintf (dump_file, "\n");
1345 unsigned v = SSA_NAME_VERSION (ssa);
1347 bitmap_set_bit (m_killed_defs, v);
1348 bitmap_set_bit (m_equiv.m_names, v);
1350 // Now add an equivalency with itself so we don't look to the root oracle.
1351 bitmap b = BITMAP_ALLOC (&m_bitmaps);
1352 bitmap_set_bit (b, v);
1353 equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1354 sizeof (equiv_chain));
1355 ptr->m_names = b;
1356 ptr->m_bb = NULL;
1357 ptr->m_next = m_equiv.m_next;
1358 m_equiv.m_next = ptr;
1360 // Walk the relation list and remove SSA from any relations.
1361 if (!bitmap_bit_p (m_relations.m_names, v))
1362 return;
1364 bitmap_clear_bit (m_relations.m_names, v);
1365 relation_chain **prev = &(m_relations.m_head);
1366 relation_chain *next = NULL;
1367 for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
1369 gcc_checking_assert (*prev == ptr);
1370 next = ptr->m_next;
1371 if (SSA_NAME_VERSION (ptr->op1 ()) == v
1372 || SSA_NAME_VERSION (ptr->op2 ()) == v)
1373 *prev = ptr->m_next;
1374 else
1375 prev = &(ptr->m_next);
1379 // Register relation K between SSA1 and SSA2, resolving unknowns by
1380 // querying from BB.
1382 void
1383 path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
1384 tree ssa2)
1386 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1387 // and no other relation makes sense.
1388 if (ssa1 == ssa2)
1389 return;
1391 if (dump_file && (dump_flags & TDF_DETAILS))
1393 value_relation vr (k, ssa1, ssa2);
1394 fprintf (dump_file, " Registering value_relation (path_oracle) ");
1395 vr.dump (dump_file);
1396 fprintf (dump_file, " (root: bb%d)\n", bb->index);
1399 relation_kind curr = query_relation (bb, ssa1, ssa2);
1400 if (curr != VREL_VARYING)
1401 k = relation_intersect (curr, k);
1403 if (k == VREL_EQ)
1405 register_equiv (bb, ssa1, ssa2);
1406 return;
1409 bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
1410 bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
1411 relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1412 sizeof (relation_chain));
1413 ptr->set_relation (k, ssa1, ssa2);
1414 ptr->m_next = m_relations.m_head;
1415 m_relations.m_head = ptr;
1418 // Query for a relationship between equiv set B1 and B2, resolving unknowns
1419 // starting at block BB.
1421 relation_kind
1422 path_oracle::query_relation (basic_block bb, const_bitmap b1, const_bitmap b2)
1424 if (bitmap_equal_p (b1, b2))
1425 return VREL_EQ;
1427 relation_kind k = m_relations.find_relation (b1, b2);
1429 // Do not look at the root oracle for names that have been killed
1430 // along the path.
1431 if (bitmap_intersect_p (m_killed_defs, b1)
1432 || bitmap_intersect_p (m_killed_defs, b2))
1433 return k;
1435 if (k == VREL_VARYING && m_root)
1436 k = m_root->query_relation (bb, b1, b2);
1438 return k;
1441 // Query for a relationship between SSA1 and SSA2, resolving unknowns
1442 // starting at block BB.
1444 relation_kind
1445 path_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1447 unsigned v1 = SSA_NAME_VERSION (ssa1);
1448 unsigned v2 = SSA_NAME_VERSION (ssa2);
1450 if (v1 == v2)
1451 return VREL_EQ;
1453 const_bitmap equiv_1 = equiv_set (ssa1, bb);
1454 const_bitmap equiv_2 = equiv_set (ssa2, bb);
1455 if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
1456 return VREL_EQ;
1458 return query_relation (bb, equiv_1, equiv_2);
1461 // Reset any relations registered on this path. ORACLE is the root
1462 // oracle to use.
1464 void
1465 path_oracle::reset_path (relation_oracle *oracle)
1467 set_root_oracle (oracle);
1468 m_equiv.m_next = NULL;
1469 bitmap_clear (m_equiv.m_names);
1470 m_relations.m_head = NULL;
1471 bitmap_clear (m_relations.m_names);
1472 bitmap_clear (m_killed_defs);
1475 // Dump relation in basic block... Do nothing here.
1477 void
1478 path_oracle::dump (FILE *, basic_block) const
1482 // Dump the relations and equivalencies found in the path.
1484 void
1485 path_oracle::dump (FILE *f) const
1487 equiv_chain *ptr = m_equiv.m_next;
1488 relation_chain *ptr2 = m_relations.m_head;
1490 if (ptr || ptr2)
1491 fprintf (f, "\npath_oracle:\n");
1493 for (; ptr; ptr = ptr->m_next)
1494 ptr->dump (f);
1496 for (; ptr2; ptr2 = ptr2->m_next)
1498 fprintf (f, "Relational : ");
1499 ptr2->dump (f);
1500 fprintf (f, "\n");