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