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 38683 : print_relation (FILE *f, relation_kind rel)
43 : {
44 38683 : fprintf (f, " %s ", kind_string[rel]);
45 38683 : }
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 18480677 : relation_swap (relation_kind r)
69 : {
70 18480677 : 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 93676728 : relation_intersect (relation_kind r1, relation_kind r2)
106 : {
107 93676728 : 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 85237188 : relation_union (relation_kind r1, relation_kind r2)
143 : {
144 85237188 : 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 8987757 : relation_transitive (relation_kind r1, relation_kind r2)
182 : {
183 8987757 : 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 1723448 : adjust_equivalence_range (vrange &range)
192 : {
193 1723448 : if (range.undefined_p () || !is_a<frange> (range))
194 1690053 : return;
195 :
196 33395 : frange fr = as_a<frange> (range);
197 : // If range includes 0 make sure both signs of zero are included.
198 33395 : if (fr.contains_p (dconst0) || fr.contains_p (dconstm0))
199 : {
200 17109 : frange zeros (range.type (), dconstm0, dconst0);
201 17109 : range.union_ (zeros);
202 17109 : }
203 33395 : }
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 19941878 : relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
210 : {
211 19941878 : unsigned i;
212 19941878 : bitmap_iterator bi;
213 41565795 : EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
214 : {
215 21623917 : tree ssa = ssa_name (i);
216 43247833 : if (ssa && !SSA_NAME_IN_FREE_LIST (ssa))
217 : {
218 21623916 : const_bitmap ssa_equiv = equiv_set (ssa, bb);
219 21623916 : if (ssa_equiv == equivs)
220 21404599 : bitmap_set_bit (b, i);
221 : }
222 : }
223 19941878 : }
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 109440289 : relation_oracle::query (gimple *s, tree ssa1, tree ssa2)
231 : {
232 109440289 : if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
233 : return VREL_VARYING;
234 40512737 : 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 53830505 : relation_oracle::query (edge e, tree ssa1, tree ssa2)
243 : {
244 53830505 : basic_block bb;
245 53830505 : 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 39900610 : if (!single_pred_p (e->dest))
252 38173502 : bb = e->src;
253 : else
254 : bb = e->dest;
255 :
256 39900610 : 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 168603128 : equiv_chain::find (unsigned ssa)
273 : {
274 168603128 : 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 168603128 : if (bitmap_bit_p (m_names, ssa))
278 : {
279 211223038 : for (ptr = m_next; ptr; ptr = ptr->m_next)
280 211223038 : if (bitmap_bit_p (ptr->m_names, ssa))
281 : break;
282 : }
283 168603128 : 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 25418327 : equiv_oracle::equiv_oracle ()
313 : {
314 25418327 : bitmap_obstack_initialize (&m_bitmaps);
315 25418327 : m_equiv.create (0);
316 25418327 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
317 25418327 : m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
318 25418327 : bitmap_tree_view (m_equiv_set);
319 25418327 : obstack_init (&m_chain_obstack);
320 25418327 : m_self_equiv.create (0);
321 50836654 : m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
322 25418327 : m_partial.create (0);
323 50836654 : m_partial.safe_grow_cleared (num_ssa_names + 1);
324 : // Create a bitmap to avoid registering multiple equivalences from a LHS.
325 : // See PR 124809.
326 25418327 : m_lhs_equiv_set_p = BITMAP_ALLOC (&m_bitmaps);
327 25418327 : bitmap_tree_view (m_lhs_equiv_set_p);
328 25418327 : }
329 :
330 : // Destruct an equivalency oracle.
331 :
332 25418327 : equiv_oracle::~equiv_oracle ()
333 : {
334 25418327 : m_partial.release ();
335 25418327 : m_self_equiv.release ();
336 25418327 : obstack_free (&m_chain_obstack, NULL);
337 25418327 : m_equiv.release ();
338 25418327 : bitmap_obstack_release (&m_bitmaps);
339 25418327 : }
340 :
341 : // Add a partial equivalence R between OP1 and OP2. Return false if no
342 : // new relation is added.
343 :
344 : bool
345 9675405 : equiv_oracle::add_partial_equiv (relation_kind r, tree op1, tree op2)
346 : {
347 9675405 : int v1 = SSA_NAME_VERSION (op1);
348 9675405 : int v2 = SSA_NAME_VERSION (op2);
349 9675405 : int prec2 = TYPE_PRECISION (TREE_TYPE (op2));
350 9675405 : int bits = pe_to_bits (r);
351 9675405 : gcc_checking_assert (bits && prec2 >= bits);
352 :
353 19350810 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
354 370 : m_partial.safe_grow_cleared (num_ssa_names + 1);
355 19350810 : gcc_checking_assert (v1 < (int)m_partial.length ()
356 : && v2 < (int)m_partial.length ());
357 :
358 9675405 : pe_slice &pe1 = m_partial[v1];
359 9675405 : pe_slice &pe2 = m_partial[v2];
360 :
361 9675405 : if (pe1.members)
362 : {
363 : // If the definition pe1 already has an entry, either the stmt is
364 : // being re-evaluated, or the def was used before being registered.
365 : // In either case, if PE2 has an entry, we simply do nothing.
366 356 : if (pe2.members)
367 : return false;
368 : // If there are no uses of op2, do not register.
369 225 : if (has_zero_uses (op2))
370 : return false;
371 : // PE1 is the LHS and already has members, so everything in the set
372 : // should be a slice of PE2 rather than PE1.
373 225 : pe2.code = pe_min (r, pe1.code);
374 225 : pe2.ssa_base = op2;
375 225 : pe2.members = pe1.members;
376 225 : bitmap_iterator bi;
377 225 : unsigned x;
378 676 : EXECUTE_IF_SET_IN_BITMAP (pe1.members, 0, x, bi)
379 : {
380 451 : m_partial[x].ssa_base = op2;
381 451 : m_partial[x].code = pe_min (m_partial[x].code, pe2.code);
382 : }
383 225 : bitmap_set_bit (pe1.members, v2);
384 225 : return true;
385 : }
386 9675049 : if (pe2.members)
387 : {
388 : // If there are no uses of op1, do not register.
389 700618 : if (has_zero_uses (op1))
390 : return false;
391 693718 : pe1.ssa_base = pe2.ssa_base;
392 : // If pe2 is a 16 bit value, but only an 8 bit copy, we can't be any
393 : // more than an 8 bit equivalence here, so choose MIN value.
394 693718 : pe1.code = pe_min (r, pe2.code);
395 693718 : pe1.members = pe2.members;
396 693718 : bitmap_set_bit (pe1.members, v1);
397 : }
398 : else
399 : {
400 : // If there are no uses of either operand, do not register.
401 8974431 : if (has_zero_uses (op1) || has_zero_uses (op2))
402 : return false;
403 : // Neither name has an entry, simply create op1 as slice of op2.
404 8871307 : pe2.code = bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2)));
405 8871307 : if (pe2.code == VREL_VARYING)
406 : return false;
407 8844709 : pe2.ssa_base = op2;
408 8844709 : pe2.members = BITMAP_ALLOC (&m_bitmaps);
409 8844709 : bitmap_set_bit (pe2.members, v2);
410 8844709 : pe1.ssa_base = op2;
411 8844709 : pe1.code = r;
412 8844709 : pe1.members = pe2.members;
413 8844709 : bitmap_set_bit (pe1.members, v1);
414 : }
415 : return true;
416 : }
417 :
418 : // Return the set of partial equivalences associated with NAME. The bitmap
419 : // will be NULL if there are none.
420 :
421 : const pe_slice *
422 56547498 : equiv_oracle::partial_equiv_set (tree name)
423 : {
424 56547498 : int v = SSA_NAME_VERSION (name);
425 113094996 : if (v >= (int)m_partial.length ())
426 : return NULL;
427 56547498 : return &m_partial[v];
428 : }
429 :
430 : // Query if there is a partial equivalence between SSA1 and SSA2. Return
431 : // VREL_VARYING if there is not one. If BASE is non-null, return the base
432 : // ssa-name this is a slice of.
433 :
434 : relation_kind
435 57163146 : equiv_oracle::partial_equiv (tree ssa1, tree ssa2, tree *base) const
436 : {
437 57163146 : int v1 = SSA_NAME_VERSION (ssa1);
438 57163146 : int v2 = SSA_NAME_VERSION (ssa2);
439 :
440 114326292 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
441 : return VREL_VARYING;
442 :
443 57162866 : const pe_slice &pe1 = m_partial[v1];
444 57162866 : const pe_slice &pe2 = m_partial[v2];
445 57162866 : if (pe1.members && pe2.members == pe1.members)
446 : {
447 1622 : if (base)
448 0 : *base = pe1.ssa_base;
449 1622 : return pe_min (pe1.code, pe2.code);
450 : }
451 : return VREL_VARYING;
452 : }
453 :
454 :
455 : // Find and return the equivalency set for SSA along the dominators of BB.
456 : // This is the external API.
457 :
458 : const_bitmap
459 143474946 : equiv_oracle::equiv_set (tree ssa, basic_block bb)
460 : {
461 : // Search the dominator tree for an equivalency.
462 143474946 : equiv_chain *equiv = find_equiv_dom (ssa, bb);
463 143474946 : if (equiv)
464 17176895 : return equiv->m_names;
465 :
466 : // Otherwise return a cached equiv set containing just this SSA.
467 126298051 : unsigned v = SSA_NAME_VERSION (ssa);
468 126298051 : if (v >= m_self_equiv.length ())
469 52 : m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
470 :
471 126298051 : if (!m_self_equiv[v])
472 : {
473 34353511 : m_self_equiv[v] = BITMAP_ALLOC (&m_bitmaps);
474 34353511 : bitmap_set_bit (m_self_equiv[v], v);
475 : }
476 126298051 : return m_self_equiv[v];
477 : }
478 :
479 : // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
480 :
481 : relation_kind
482 0 : equiv_oracle::query (basic_block bb, tree ssa1, tree ssa2)
483 : {
484 : // If the 2 ssa names share the same equiv set, they are equal.
485 0 : if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb))
486 : return VREL_EQ;
487 :
488 : // Check if there is a partial equivalence.
489 0 : return partial_equiv (ssa1, ssa2);
490 : }
491 :
492 : // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
493 :
494 : relation_kind
495 0 : equiv_oracle::query (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1,
496 : const_bitmap e2)
497 : {
498 : // If the 2 ssa names share the same equiv set, they are equal.
499 0 : if (bitmap_equal_p (e1, e2))
500 0 : return VREL_EQ;
501 : return VREL_VARYING;
502 : }
503 :
504 : // If SSA has an equivalence in block BB, find and return it.
505 : // Otherwise return NULL.
506 :
507 : equiv_chain *
508 103733584 : equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
509 : {
510 207467168 : if (bb >= (int)m_equiv.length () || !m_equiv[bb])
511 : return NULL;
512 :
513 45372944 : return m_equiv[bb]->find (ssa);
514 : }
515 :
516 : // Starting at block BB, walk the dominator chain looking for the nearest
517 : // equivalence set containing NAME.
518 :
519 : equiv_chain *
520 158115281 : equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
521 : {
522 158115281 : unsigned v = SSA_NAME_VERSION (name);
523 : // Short circuit looking for names which have no equivalences.
524 : // Saves time looking for something which does not exist.
525 158115281 : if (!bitmap_bit_p (m_equiv_set, v))
526 : return NULL;
527 :
528 : // NAME has at least once equivalence set, check to see if it has one along
529 : // the dominator tree.
530 104807016 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
531 : {
532 103733584 : equiv_chain *ptr = find_equiv_block (v, bb->index);
533 103733584 : if (ptr)
534 : return ptr;
535 : }
536 : return NULL;
537 : }
538 :
539 : // Register equivalence between ssa_name V and set EQUIV in block BB,
540 :
541 : bitmap
542 74794 : equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
543 : {
544 : // V will have an equivalency now.
545 74794 : bitmap_set_bit (m_equiv_set, v);
546 :
547 : // If that equiv chain is in this block, simply use it.
548 74794 : if (equiv->m_bb == bb)
549 : {
550 16050 : bitmap_set_bit (equiv->m_names, v);
551 16050 : bitmap_set_bit (m_equiv[bb->index]->m_names, v);
552 16050 : return NULL;
553 : }
554 :
555 : // Otherwise create an equivalence for this block which is a copy
556 : // of equiv, the add V to the set.
557 58744 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
558 58744 : valid_equivs (b, equiv->m_names, bb);
559 58744 : bitmap_set_bit (b, v);
560 58744 : return b;
561 : }
562 :
563 : // Register equivalence between set equiv_1 and equiv_2 in block BB.
564 : // Return NULL if either name can be merged with the other. Otherwise
565 : // return a pointer to the combined bitmap of names. This allows the
566 : // caller to do any setup required for a new element.
567 :
568 : bitmap
569 3770795 : equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
570 : equiv_chain *equiv_2)
571 : {
572 : // If equiv_1 is already in BB, use it as the combined set.
573 3770795 : if (equiv_1->m_bb == bb)
574 : {
575 2066896 : valid_equivs (equiv_1->m_names, equiv_2->m_names, bb);
576 : // Its hard to delete from a single linked list, so
577 : // just clear the second one.
578 2066896 : if (equiv_2->m_bb == bb)
579 336801 : bitmap_clear (equiv_2->m_names);
580 : else
581 : // Ensure the new names are in the summary for BB.
582 1730095 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
583 2066896 : return NULL;
584 : }
585 : // If equiv_2 is in BB, use it for the combined set.
586 1703899 : if (equiv_2->m_bb == bb)
587 : {
588 2214 : valid_equivs (equiv_2->m_names, equiv_1->m_names, bb);
589 : // Ensure the new names are in the summary.
590 2214 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
591 2214 : return NULL;
592 : }
593 :
594 : // At this point, neither equivalence is from this block.
595 1701685 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
596 1701685 : valid_equivs (b, equiv_1->m_names, bb);
597 1701685 : valid_equivs (b, equiv_2->m_names, bb);
598 1701685 : return b;
599 : }
600 :
601 : // Create an equivalency set containing only SSA in its definition block.
602 : // This is done the first time SSA is registered in an equivalency and blocks
603 : // any DOM searches past the definition.
604 :
605 : void
606 7009208 : equiv_oracle::register_initial_def (tree ssa)
607 : {
608 7009208 : if (SSA_NAME_IS_DEFAULT_DEF (ssa))
609 : return;
610 6926672 : basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
611 :
612 : // If defining stmt is not in the IL, simply return.
613 6926672 : if (!bb)
614 : return;
615 6926671 : gcc_checking_assert (!find_equiv_dom (ssa, bb));
616 :
617 6926671 : unsigned v = SSA_NAME_VERSION (ssa);
618 6926671 : bitmap_set_bit (m_equiv_set, v);
619 6926671 : bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps);
620 6926671 : bitmap_set_bit (equiv_set, v);
621 6926671 : add_equiv_to_block (bb, equiv_set);
622 : }
623 :
624 : // Register an equivalence between SSA1 and SSA2 in block BB.
625 : // The equivalence oracle maintains a vector of equivalencies indexed by basic
626 : // block. When an equivalence between SSA1 and SSA2 is registered in block BB,
627 : // a query is made as to what equivalences both names have already, and
628 : // any preexisting equivalences are merged to create a single equivalence
629 : // containing all the ssa_names in this basic block.
630 : // Return false if no new relation is added.
631 :
632 : bool
633 13532237 : equiv_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
634 : {
635 : // Process partial equivalencies.
636 13532237 : if (relation_partial_equiv_p (k))
637 9675405 : return add_partial_equiv (k, ssa1, ssa2);
638 :
639 : // Only handle equality relations.
640 3856832 : if (k != VREL_EQ)
641 : return false;
642 :
643 3856832 : unsigned v1 = SSA_NAME_VERSION (ssa1);
644 3856832 : unsigned v2 = SSA_NAME_VERSION (ssa2);
645 :
646 : // If this is the first time an ssa_name has an equivalency registered
647 : // create a self-equivalency record in the def block.
648 3856832 : if (!bitmap_bit_p (m_equiv_set, v1))
649 3708822 : register_initial_def (ssa1);
650 3856832 : if (!bitmap_bit_p (m_equiv_set, v2))
651 3300386 : register_initial_def (ssa2);
652 :
653 3856832 : equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
654 3856832 : equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
655 :
656 : // Check if they are the same set
657 3856832 : if (equiv_1 && equiv_1 == equiv_2)
658 : return false;
659 :
660 3855089 : bitmap equiv_set;
661 :
662 : // Case where we have 2 SSA_NAMEs that are not in any set.
663 3855089 : if (!equiv_1 && !equiv_2)
664 : {
665 9500 : bitmap_set_bit (m_equiv_set, v1);
666 9500 : bitmap_set_bit (m_equiv_set, v2);
667 :
668 9500 : equiv_set = BITMAP_ALLOC (&m_bitmaps);
669 9500 : bitmap_set_bit (equiv_set, v1);
670 9500 : bitmap_set_bit (equiv_set, v2);
671 : }
672 3845589 : else if (!equiv_1 && equiv_2)
673 22317 : equiv_set = register_equiv (bb, v1, equiv_2);
674 3823272 : else if (equiv_1 && !equiv_2)
675 52477 : equiv_set = register_equiv (bb, v2, equiv_1);
676 : else
677 3770795 : equiv_set = register_equiv (bb, equiv_1, equiv_2);
678 :
679 : // A non-null return is a bitmap that is to be added to the current
680 : // block as a new equivalence.
681 3855089 : if (!equiv_set)
682 : return false;
683 :
684 1769929 : add_equiv_to_block (bb, equiv_set);
685 1769929 : return true;
686 : }
687 :
688 : // Add an equivalency record in block BB containing bitmap EQUIV_SET.
689 : // Note the internal caller is responsible for allocating EQUIV_SET properly.
690 :
691 : void
692 8696600 : equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
693 : {
694 8696600 : equiv_chain *ptr;
695 :
696 : // Check if this is the first time a block has an equivalence added.
697 : // and create a header block. And set the summary for this block.
698 8696600 : limit_check (bb);
699 8696600 : if (!m_equiv[bb->index])
700 : {
701 5599440 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
702 : sizeof (equiv_chain));
703 5599440 : ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
704 5599440 : bitmap_copy (ptr->m_names, equiv_set);
705 5599440 : ptr->m_bb = bb;
706 5599440 : ptr->m_next = NULL;
707 5599440 : m_equiv[bb->index] = ptr;
708 : }
709 :
710 : // Now create the element for this equiv set and initialize it.
711 8696600 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
712 8696600 : ptr->m_names = equiv_set;
713 8696600 : ptr->m_bb = bb;
714 17393200 : gcc_checking_assert (bb->index < (int)m_equiv.length ());
715 8696600 : ptr->m_next = m_equiv[bb->index]->m_next;
716 8696600 : m_equiv[bb->index]->m_next = ptr;
717 8696600 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
718 8696600 : }
719 :
720 : // Make sure the BB vector is big enough and grow it if needed.
721 :
722 : void
723 8696600 : equiv_oracle::limit_check (basic_block bb)
724 : {
725 8696600 : int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
726 17393200 : if (i >= (int)m_equiv.length ())
727 43 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
728 8696600 : }
729 :
730 : // Dump the equivalence sets in BB to file F.
731 :
732 : void
733 248 : equiv_oracle::dump (FILE *f, basic_block bb) const
734 : {
735 496 : if (bb->index >= (int)m_equiv.length ())
736 : return;
737 : // Process equivalences.
738 248 : if (m_equiv[bb->index])
739 : {
740 9 : equiv_chain *ptr = m_equiv[bb->index]->m_next;
741 20 : for (; ptr; ptr = ptr->m_next)
742 11 : ptr->dump (f);
743 : }
744 : // Look for partial equivalences defined in this block..
745 12841 : for (unsigned i = 0; i < num_ssa_names; i++)
746 : {
747 12593 : tree name = ssa_name (i);
748 17805 : if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name))
749 7381 : continue;
750 5212 : if (i >= m_partial.length ())
751 : break;
752 5212 : tree base = m_partial[i].ssa_base;
753 5212 : if (base && name != base && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb)
754 : {
755 42 : relation_kind k = partial_equiv (name, base);
756 42 : if (k != VREL_VARYING)
757 : {
758 42 : value_relation vr (k, name, base);
759 42 : fprintf (f, "Partial equiv ");
760 42 : vr.dump (f);
761 42 : fputc ('\n',f);
762 : }
763 : }
764 : }
765 : }
766 :
767 : // Dump all equivalence sets known to the oracle.
768 :
769 : void
770 0 : equiv_oracle::dump (FILE *f) const
771 : {
772 0 : fprintf (f, "Equivalency dump\n");
773 0 : for (unsigned i = 0; i < m_equiv.length (); i++)
774 0 : if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
775 : {
776 0 : fprintf (f, "BB%d\n", i);
777 0 : dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
778 : }
779 0 : }
780 :
781 :
782 : // --------------------------------------------------------------------------
783 :
784 : // Adjust the relation by Swapping the operands and relation.
785 :
786 : void
787 0 : value_relation::swap ()
788 : {
789 0 : related = relation_swap (related);
790 0 : tree tmp = name1;
791 0 : name1 = name2;
792 0 : name2 = tmp;
793 0 : }
794 :
795 : // Perform an intersection between 2 relations. *this &&= p.
796 : // Return false if the relations cannot be intersected.
797 :
798 : bool
799 4534896 : value_relation::intersect (value_relation &p)
800 : {
801 : // Save previous value
802 4534896 : relation_kind old = related;
803 :
804 4534896 : if (p.op1 () == op1 () && p.op2 () == op2 ())
805 4534553 : related = relation_intersect (kind (), p.kind ());
806 343 : else if (p.op2 () == op1 () && p.op1 () == op2 ())
807 343 : related = relation_intersect (kind (), relation_swap (p.kind ()));
808 : else
809 : return false;
810 :
811 4534896 : return old != related;
812 : }
813 :
814 : // Perform a union between 2 relations. *this ||= p.
815 :
816 : bool
817 0 : value_relation::union_ (value_relation &p)
818 : {
819 : // Save previous value
820 0 : relation_kind old = related;
821 :
822 0 : if (p.op1 () == op1 () && p.op2 () == op2 ())
823 0 : related = relation_union (kind(), p.kind());
824 0 : else if (p.op2 () == op1 () && p.op1 () == op2 ())
825 0 : related = relation_union (kind(), relation_swap (p.kind ()));
826 : else
827 : return false;
828 :
829 0 : return old != related;
830 : }
831 :
832 : // Identify and apply any transitive relations between REL
833 : // and THIS. Return true if there was a transformation.
834 :
835 : bool
836 13873479 : value_relation::apply_transitive (const value_relation &rel)
837 : {
838 13873479 : relation_kind k = VREL_VARYING;
839 :
840 : // Identify any common operand, and normalize the relations to
841 : // the form : A < B B < C produces A < C
842 13873479 : if (rel.op1 () == name2)
843 : {
844 : // A < B B < C
845 2275137 : if (rel.op2 () == name1)
846 : return false;
847 2206136 : k = relation_transitive (kind (), rel.kind ());
848 2206136 : if (k != VREL_VARYING)
849 : {
850 915688 : related = k;
851 915688 : name2 = rel.op2 ();
852 915688 : return true;
853 : }
854 : }
855 11598342 : else if (rel.op1 () == name1)
856 : {
857 : // B > A B < C
858 6726431 : if (rel.op2 () == name2)
859 : return false;
860 1909710 : k = relation_transitive (relation_swap (kind ()), rel.kind ());
861 1909710 : if (k != VREL_VARYING)
862 : {
863 487863 : related = k;
864 487863 : name1 = name2;
865 487863 : name2 = rel.op2 ();
866 487863 : return true;
867 : }
868 : }
869 4871911 : else if (rel.op2 () == name2)
870 : {
871 : // A < B C > B
872 4246109 : if (rel.op1 () == name1)
873 : return false;
874 4246109 : k = relation_transitive (kind (), relation_swap (rel.kind ()));
875 4246109 : if (k != VREL_VARYING)
876 : {
877 540332 : related = k;
878 540332 : name2 = rel.op1 ();
879 540332 : return true;
880 : }
881 : }
882 625802 : else if (rel.op2 () == name1)
883 : {
884 : // B > A C > B
885 625802 : if (rel.op1 () == name2)
886 : return false;
887 625802 : k = relation_transitive (relation_swap (kind ()),
888 : relation_swap (rel.kind ()));
889 625802 : if (k != VREL_VARYING)
890 : {
891 242654 : related = k;
892 242654 : name1 = name2;
893 242654 : name2 = rel.op1 ();
894 242654 : return true;
895 : }
896 : }
897 : return false;
898 : }
899 :
900 : // Create a trio from this value relation given LHS, OP1 and OP2.
901 :
902 : relation_trio
903 51148325 : value_relation::create_trio (tree lhs, tree op1, tree op2)
904 : {
905 51148325 : relation_kind lhs_1;
906 51148325 : if (lhs == name1 && op1 == name2)
907 71293 : lhs_1 = related;
908 51077032 : else if (lhs == name2 && op1 == name1)
909 177843 : lhs_1 = relation_swap (related);
910 : else
911 : lhs_1 = VREL_VARYING;
912 :
913 51148325 : relation_kind lhs_2;
914 51148325 : if (lhs == name1 && op2 == name2)
915 53879 : lhs_2 = related;
916 51094446 : else if (lhs == name2 && op2 == name1)
917 152654 : lhs_2 = relation_swap (related);
918 : else
919 : lhs_2 = VREL_VARYING;
920 :
921 51148325 : relation_kind op_op;
922 51148325 : if (op1 == name1 && op2 == name2)
923 35808008 : op_op = related;
924 15340317 : else if (op1 == name2 && op2 == name1)
925 0 : op_op = relation_swap (related);
926 15340317 : else if (op1 == op2)
927 : op_op = VREL_EQ;
928 : else
929 15325707 : op_op = VREL_VARYING;
930 :
931 51148325 : return relation_trio (lhs_1, lhs_2, op_op);
932 : }
933 :
934 : // Dump the relation to file F.
935 :
936 : void
937 38560 : value_relation::dump (FILE *f) const
938 : {
939 38560 : if (!name1 || !name2)
940 : {
941 0 : fprintf (f, "no relation registered");
942 0 : return;
943 : }
944 38560 : fputc ('(', f);
945 38560 : print_generic_expr (f, op1 (), TDF_SLIM);
946 38560 : print_relation (f, kind ());
947 38560 : print_generic_expr (f, op2 (), TDF_SLIM);
948 38560 : fputc(')', f);
949 : }
950 :
951 : // This container is used to link relations in a chain.
952 :
953 : class relation_chain : public value_relation
954 : {
955 : public:
956 : relation_chain *m_next;
957 : };
958 :
959 : // Given relation record PTR in block BB, return the next relation in the
960 : // list. If PTR is NULL, retreive the first relation in BB.
961 : // If NAME is sprecified, return only relations which include NAME.
962 : // Return NULL when there are no relations left.
963 :
964 : relation_chain *
965 84 : dom_oracle::next_relation (basic_block bb, relation_chain *ptr,
966 : tree name) const
967 : {
968 84 : relation_chain *p;
969 : // No value_relation pointer is used to intialize the iterator.
970 84 : if (!ptr)
971 : {
972 37 : int bbi = bb->index;
973 74 : if (bbi >= (int)m_relations.length())
974 : return NULL;
975 : else
976 37 : p = m_relations[bbi].m_head;
977 : }
978 : else
979 47 : p = ptr->m_next;
980 :
981 84 : if (name)
982 0 : for ( ; p; p = p->m_next)
983 0 : if (p->op1 () == name || p->op2 () == name)
984 : break;
985 : return p;
986 : }
987 :
988 : // Instatiate a block relation iterator to iterate over the relations
989 : // on exit from block BB in ORACLE. Limit this to relations involving NAME
990 : // if specified. Return the first such relation in VR if there is one.
991 :
992 37 : block_relation_iterator::block_relation_iterator (const relation_oracle *oracle,
993 : basic_block bb,
994 : value_relation &vr,
995 37 : tree name)
996 : {
997 37 : m_oracle = oracle;
998 37 : m_bb = bb;
999 37 : m_name = name;
1000 37 : m_ptr = oracle->next_relation (bb, NULL, m_name);
1001 37 : if (m_ptr)
1002 : {
1003 37 : m_done = false;
1004 37 : vr = *m_ptr;
1005 : }
1006 : else
1007 0 : m_done = true;
1008 37 : }
1009 :
1010 : // Retreive the next relation from the iterator and return it in VR.
1011 :
1012 : void
1013 47 : block_relation_iterator::get_next_relation (value_relation &vr)
1014 : {
1015 47 : m_ptr = m_oracle->next_relation (m_bb, m_ptr, m_name);
1016 47 : if (m_ptr)
1017 : {
1018 10 : vr = *m_ptr;
1019 10 : if (m_name)
1020 : {
1021 0 : if (vr.op1 () != m_name)
1022 : {
1023 0 : gcc_checking_assert (vr.op2 () == m_name);
1024 0 : vr.swap ();
1025 : }
1026 : }
1027 : }
1028 : else
1029 37 : m_done = true;
1030 47 : }
1031 :
1032 : // ------------------------------------------------------------------------
1033 :
1034 : // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
1035 : // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1036 :
1037 : relation_kind
1038 288509488 : relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
1039 : {
1040 288509488 : if (!m_names)
1041 : return VREL_VARYING;
1042 :
1043 : // If both b1 and b2 aren't referenced in this block, cant be a relation
1044 173648234 : if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
1045 169418712 : return VREL_VARYING;
1046 :
1047 : // Search for the first relation that contains BOTH an element from B1
1048 : // and B2, and return that relation.
1049 15036566 : for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
1050 : {
1051 13291923 : unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1052 13291923 : unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1053 13291923 : if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
1054 2346108 : return ptr->kind ();
1055 10945815 : if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
1056 138771 : return relation_swap (ptr->kind ());
1057 : }
1058 :
1059 : return VREL_VARYING;
1060 : }
1061 :
1062 : // Instantiate a relation oracle.
1063 :
1064 25418327 : dom_oracle::dom_oracle (bool do_trans_p)
1065 : {
1066 25418327 : m_do_trans_p = do_trans_p;
1067 25418327 : m_relations.create (0);
1068 25418327 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1069 25418327 : m_relation_set = BITMAP_ALLOC (&m_bitmaps);
1070 25418327 : m_tmp = BITMAP_ALLOC (&m_bitmaps);
1071 25418327 : m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
1072 25418327 : }
1073 :
1074 : // Destruct a relation oracle.
1075 :
1076 50836654 : dom_oracle::~dom_oracle ()
1077 : {
1078 25418327 : m_relations.release ();
1079 50836654 : }
1080 :
1081 : // Register relation K between ssa_name OP1 and OP2 on STMT.
1082 : // Return false if no new relation is added.
1083 :
1084 : bool
1085 32313359 : relation_oracle::record (gimple *stmt, relation_kind k, tree op1, tree op2)
1086 : {
1087 32313359 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1088 32313359 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1089 32313359 : gcc_checking_assert (stmt && gimple_bb (stmt));
1090 :
1091 : // Don't register lack of a relation.
1092 32313359 : if (k == VREL_VARYING)
1093 : return false;
1094 :
1095 : // If an equivalence is being added between a PHI and one of its arguments
1096 : // make sure that that argument is not defined in the same block.
1097 : // This can happen along back edges and the equivalence will not be
1098 : // applicable as it would require a use before def.
1099 32313359 : if (k == VREL_EQ && is_a<gphi *> (stmt))
1100 : {
1101 1888828 : tree phi_def = gimple_phi_result (stmt);
1102 1888828 : gcc_checking_assert (phi_def == op1 || phi_def == op2);
1103 1888828 : tree arg = op2;
1104 1888828 : if (phi_def == op2)
1105 0 : arg = op1;
1106 1888828 : if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
1107 : return false;
1108 : }
1109 :
1110 : // If the LHS of a statement has already been processed and an equivalence
1111 : // registered, do not register another one. See PR 124809.
1112 76383811 : if (m_lhs_equiv_set_p && relation_equiv_p (k)
1113 44856794 : && gimple_get_lhs (stmt) == op1)
1114 : {
1115 12543435 : if (!bitmap_set_bit (m_lhs_equiv_set_p, SSA_NAME_VERSION (op1)))
1116 : return false;
1117 : }
1118 31527017 : bool ret = record (gimple_bb (stmt), k, op1, op2);
1119 :
1120 31527017 : if (ret && dump_file && (dump_flags & TDF_DETAILS))
1121 : {
1122 36751 : value_relation vr (k, op1, op2);
1123 36751 : fprintf (dump_file, " Registering value_relation ");
1124 36751 : vr.dump (dump_file);
1125 36751 : fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
1126 36751 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1127 : }
1128 : return ret;
1129 : }
1130 :
1131 : // Register relation K between ssa_name OP1 and OP2 on edge E.
1132 : // Return false if no new relation is added.
1133 :
1134 : bool
1135 6454243 : relation_oracle::record (edge e, relation_kind k, tree op1, tree op2)
1136 : {
1137 6454243 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1138 6454243 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1139 :
1140 : // Do not register lack of relation, or blocks which have more than
1141 : // edge E for a predecessor.
1142 6454243 : if (k == VREL_VARYING || !single_pred_p (e->dest))
1143 : return false;
1144 :
1145 6454243 : bool ret = record (e->dest, k, op1, op2);
1146 :
1147 6454243 : if (ret && dump_file && (dump_flags & TDF_DETAILS))
1148 : {
1149 112 : value_relation vr (k, op1, op2);
1150 112 : fprintf (dump_file, " Registering value_relation ");
1151 112 : vr.dump (dump_file);
1152 112 : fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
1153 : }
1154 : return ret;
1155 : }
1156 :
1157 : // Register relation K between OP! and OP2 in block BB.
1158 : // This creates the record and searches for existing records in the dominator
1159 : // tree to merge with. Return false if no new relation is added.
1160 :
1161 : bool
1162 36861842 : dom_oracle::record (basic_block bb, relation_kind k, tree op1, tree op2)
1163 : {
1164 : // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1165 : // and no other relation makes sense.
1166 36861842 : if (op1 == op2)
1167 : return false;
1168 :
1169 : // Equivalencies are handled by the equivalence oracle.
1170 36851132 : if (relation_equiv_p (k))
1171 13532237 : return equiv_oracle::record (bb, k, op1, op2);
1172 : else
1173 : {
1174 : // if neither op1 nor op2 are in a relation before this is registered,
1175 : // there will be no transitive.
1176 23318895 : bool check = bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op1))
1177 39068550 : || bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op2));
1178 23318895 : relation_chain *ptr = set_one_relation (bb, k, op1, op2);
1179 23318895 : if (ptr && check
1180 23318895 : && (m_relations[bb->index].m_num_relations
1181 6330522 : < param_relation_block_limit))
1182 6330386 : register_transitives (bb, *ptr);
1183 23318895 : return ptr != NULL;
1184 : }
1185 : }
1186 :
1187 : // Register relation K between OP! and OP2 in block BB.
1188 : // This creates the record and searches for existing records in the dominator
1189 : // tree to merge with. Return the record, or NULL if no record was created.
1190 :
1191 : relation_chain *
1192 25505432 : dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1,
1193 : tree op2)
1194 : {
1195 25505432 : gcc_checking_assert (k != VREL_VARYING && k != VREL_EQ);
1196 :
1197 25505432 : value_relation vr(k, op1, op2);
1198 25505432 : int bbi = bb->index;
1199 :
1200 51010864 : if (bbi >= (int)m_relations.length())
1201 137 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1202 :
1203 : // Summary bitmap indicating what ssa_names have relations in this BB.
1204 25505432 : bitmap bm = m_relations[bbi].m_names;
1205 25505432 : if (!bm)
1206 13932144 : bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
1207 25505432 : unsigned v1 = SSA_NAME_VERSION (op1);
1208 25505432 : unsigned v2 = SSA_NAME_VERSION (op2);
1209 :
1210 25505432 : relation_kind curr;
1211 25505432 : relation_chain *ptr;
1212 25505432 : curr = find_relation_block (bbi, v1, v2, &ptr);
1213 : // There is an existing relation in this block, just intersect with it.
1214 25505432 : if (curr != VREL_VARYING)
1215 : {
1216 : // Check into whether we can simply replace the relation rather than
1217 : // intersecting it. This may help with some optimistic iterative
1218 : // updating algorithms. If there was no change, return no record..
1219 4534896 : if (!ptr->intersect (vr))
1220 : return NULL;
1221 : }
1222 : else
1223 : {
1224 20970536 : if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
1225 : return NULL;
1226 20862940 : m_relations[bbi].m_num_relations++;
1227 : // Check for an existing relation further up the DOM chain.
1228 : // By including dominating relations, The first one found in any search
1229 : // will be the aggregate of all the previous ones.
1230 20862940 : curr = find_relation_dom (bb, v1, v2);
1231 20862940 : if (curr != VREL_VARYING)
1232 617766 : k = relation_intersect (curr, k);
1233 :
1234 20862940 : bitmap_set_bit (bm, v1);
1235 20862940 : bitmap_set_bit (bm, v2);
1236 20862940 : bitmap_set_bit (m_relation_set, v1);
1237 20862940 : bitmap_set_bit (m_relation_set, v2);
1238 :
1239 20862940 : ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1240 : sizeof (relation_chain));
1241 20862940 : ptr->set_relation (k, op1, op2);
1242 20862940 : ptr->m_next = m_relations[bbi].m_head;
1243 20862940 : m_relations[bbi].m_head = ptr;
1244 : }
1245 21057366 : return ptr;
1246 : }
1247 :
1248 : // Starting at ROOT_BB search the DOM tree looking for relations which
1249 : // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
1250 : // bitmaps for op1/op2 and any of their equivalences that should also be
1251 : // considered.
1252 :
1253 : void
1254 6330386 : dom_oracle::register_transitives (basic_block root_bb,
1255 : const value_relation &relation)
1256 : {
1257 : // Only register transitives if they are requested.
1258 6330386 : if (!m_do_trans_p)
1259 : return;
1260 6330376 : basic_block bb;
1261 : // Only apply transitives to certain kinds of operations.
1262 6330376 : switch (relation.kind ())
1263 : {
1264 4663798 : case VREL_LE:
1265 4663798 : case VREL_LT:
1266 4663798 : case VREL_GT:
1267 4663798 : case VREL_GE:
1268 4663798 : break;
1269 : default:
1270 : return;
1271 : }
1272 :
1273 4663798 : const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb);
1274 4663798 : const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb);
1275 :
1276 4663798 : const unsigned work_budget = param_transitive_relations_work_bound;
1277 4663798 : unsigned avail_budget = work_budget;
1278 90551463 : for (bb = root_bb; bb;
1279 : /* Advancing to the next immediate dominator eats from the budget,
1280 : if none is left after that there's no point to continue. */
1281 : bb = (--avail_budget > 0
1282 85945753 : ? get_immediate_dominator (CDI_DOMINATORS, bb) : nullptr))
1283 : {
1284 86022853 : int bbi = bb->index;
1285 172045706 : if (bbi >= (int)m_relations.length())
1286 4622 : continue;
1287 86018231 : const_bitmap bm = m_relations[bbi].m_names;
1288 86018231 : if (!bm)
1289 61478614 : continue;
1290 24539617 : if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
1291 16139235 : continue;
1292 : // At least one of the 2 ops has a relation in this block.
1293 8400382 : relation_chain *ptr;
1294 39877519 : for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
1295 : {
1296 : // In the presence of an equivalence, 2 operands may do not
1297 : // naturally match. ie with equivalence a_2 == b_3
1298 : // given c_1 < a_2 && b_3 < d_4
1299 : // convert the second relation (b_3 < d_4) to match any
1300 : // equivalences to found in the first relation.
1301 : // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1302 : // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1303 :
1304 31554237 : tree r1, r2;
1305 31554237 : tree p1 = ptr->op1 ();
1306 31554237 : tree p2 = ptr->op2 ();
1307 : // Find which equivalence is in the first operand.
1308 31554237 : if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
1309 : r1 = p1;
1310 24827307 : else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
1311 : r1 = p2;
1312 : else
1313 24132378 : r1 = NULL_TREE;
1314 :
1315 : // Find which equivalence is in the second operand.
1316 31554237 : if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
1317 : r2 = p1;
1318 29278601 : else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
1319 : r2 = p2;
1320 : else
1321 20215645 : r2 = NULL_TREE;
1322 :
1323 : // Ignore if both NULL (not relevant relation) or the same,
1324 31554237 : if (r1 == r2)
1325 : ;
1326 :
1327 : else
1328 : {
1329 : // Any operand not an equivalence, just take the real operand.
1330 13873479 : if (!r1)
1331 6452245 : r1 = relation.op1 ();
1332 13873479 : if (!r2)
1333 2535512 : r2 = relation.op2 ();
1334 :
1335 13873479 : value_relation nr (relation.kind (), r1, r2);
1336 13873479 : if (nr.apply_transitive (*ptr))
1337 : {
1338 : // If the new relation is already present we know any
1339 : // further processing is already reflected above it.
1340 : // When we ran into the limit of relations on root_bb
1341 : // we can give up as well.
1342 2186537 : if (!set_one_relation (root_bb, nr.kind (),
1343 : nr.op1 (), nr.op2 ()))
1344 70360 : return;
1345 2116177 : if (dump_file && (dump_flags & TDF_DETAILS))
1346 : {
1347 1322 : fprintf (dump_file,
1348 : " Registering transitive relation ");
1349 1322 : nr.dump (dump_file);
1350 1322 : fputc ('\n', dump_file);
1351 : }
1352 : }
1353 : }
1354 : /* Processed one relation, abort if we've eaten up our budget. */
1355 31483877 : if (--avail_budget == 0)
1356 : return;
1357 : }
1358 : }
1359 : }
1360 :
1361 : // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1362 : // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1363 :
1364 : relation_kind
1365 242246822 : dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
1366 : const_bitmap b2) const
1367 : {
1368 242246822 : if (bb >= m_relations.length())
1369 : return VREL_VARYING;
1370 :
1371 242245319 : return m_relations[bb].find_relation (b1, b2);
1372 : }
1373 :
1374 : // Search the DOM tree for a relation between an element of equivalency set B1
1375 : // and B2, starting with block BB.
1376 :
1377 : relation_kind
1378 17638352 : dom_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
1379 : {
1380 17638352 : relation_kind r;
1381 17638352 : if (bitmap_equal_p (b1, b2))
1382 : return VREL_EQ;
1383 :
1384 : // If either name does not occur in a relation anywhere, there isn't one.
1385 17638352 : if (!bitmap_intersect_p (m_relation_set, b1)
1386 17638352 : || !bitmap_intersect_p (m_relation_set, b2))
1387 8970481 : return VREL_VARYING;
1388 :
1389 : // Search each block in the DOM tree checking.
1390 250241146 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1391 : {
1392 242246822 : r = find_relation_block (bb->index, b1, b2);
1393 242246822 : if (r != VREL_VARYING)
1394 : return r;
1395 : }
1396 : return VREL_VARYING;
1397 :
1398 : }
1399 :
1400 : // Find a relation in block BB between ssa version V1 and V2. If a relation
1401 : // is found, return a pointer to the chain object in OBJ.
1402 :
1403 : relation_kind
1404 556478602 : dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
1405 : relation_chain **obj) const
1406 : {
1407 1112957204 : if (bb >= (int)m_relations.length())
1408 : return VREL_VARYING;
1409 :
1410 556472958 : const_bitmap bm = m_relations[bb].m_names;
1411 556472958 : if (!bm)
1412 : return VREL_VARYING;
1413 :
1414 : // If both b1 and b2 aren't referenced in this block, cant be a relation
1415 406058363 : if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1416 391976861 : return VREL_VARYING;
1417 :
1418 14081502 : relation_chain *ptr;
1419 77471896 : for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1420 : {
1421 74687272 : unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1422 74687272 : unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1423 74687272 : if (v1 == op1 && v2 == op2)
1424 : {
1425 11022698 : if (obj)
1426 4534553 : *obj = ptr;
1427 11022698 : return ptr->kind ();
1428 : }
1429 63664574 : if (v1 == op2 && v2 == op1)
1430 : {
1431 274180 : if (obj)
1432 343 : *obj = ptr;
1433 274180 : return relation_swap (ptr->kind ());
1434 : }
1435 : }
1436 :
1437 : return VREL_VARYING;
1438 : }
1439 :
1440 : // Find a relation between SSA version V1 and V2 in the dominator tree
1441 : // starting with block BB
1442 :
1443 : relation_kind
1444 34546366 : dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const
1445 : {
1446 34546366 : relation_kind r;
1447 : // IF either name does not occur in a relation anywhere, there isn't one.
1448 34546366 : if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1449 17928573 : return VREL_VARYING;
1450 :
1451 540828981 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1452 : {
1453 530973170 : r = find_relation_block (bb->index, v1, v2);
1454 530973170 : if (r != VREL_VARYING)
1455 : return r;
1456 : }
1457 : return VREL_VARYING;
1458 :
1459 : }
1460 :
1461 : // Query if there is a relation between SSA1 and SS2 in block BB or a
1462 : // dominator of BB
1463 :
1464 : relation_kind
1465 57523686 : dom_oracle::query (basic_block bb, tree ssa1, tree ssa2)
1466 : {
1467 57523686 : relation_kind kind;
1468 57523686 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1469 57523686 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1470 57523686 : if (v1 == v2)
1471 : return VREL_EQ;
1472 :
1473 : // If v1 or v2 do not have any relations or equivalences, a partial
1474 : // equivalence is the only possibility.
1475 94836698 : if ((!bitmap_bit_p (m_relation_set, v1) && !has_equiv_p (v1))
1476 60257218 : || (!bitmap_bit_p (m_relation_set, v2) && !has_equiv_p (v2)))
1477 43479489 : return partial_equiv (ssa1, ssa2);
1478 :
1479 : // Check for equivalence first. They must be in each equivalency set.
1480 13943934 : const_bitmap equiv1 = equiv_set (ssa1, bb);
1481 13943934 : const_bitmap equiv2 = equiv_set (ssa2, bb);
1482 13943934 : if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
1483 : return VREL_EQ;
1484 :
1485 13683615 : kind = partial_equiv (ssa1, ssa2);
1486 13683615 : if (kind != VREL_VARYING)
1487 : return kind;
1488 :
1489 : // Initially look for a direct relationship and just return that.
1490 13683426 : kind = find_relation_dom (bb, v1, v2);
1491 13683426 : if (kind != VREL_VARYING)
1492 : return kind;
1493 :
1494 : // Query using the equivalence sets.
1495 7539210 : kind = query (bb, equiv1, equiv2);
1496 7539210 : return kind;
1497 : }
1498 :
1499 : // Dump all the relations in block BB to file F.
1500 :
1501 : void
1502 248 : dom_oracle::dump (FILE *f, basic_block bb) const
1503 : {
1504 248 : equiv_oracle::dump (f,bb);
1505 :
1506 496 : if (bb->index >= (int)m_relations.length ())
1507 211 : return;
1508 248 : if (!m_relations[bb->index].m_names)
1509 : return;
1510 :
1511 37 : value_relation vr;
1512 84 : FOR_EACH_RELATION_BB (this, bb, vr)
1513 : {
1514 47 : fprintf (f, "Relational : ");
1515 47 : vr.dump (f);
1516 47 : fprintf (f, "\n");
1517 : }
1518 : }
1519 :
1520 : // Dump all the relations known to file F.
1521 :
1522 : void
1523 0 : dom_oracle::dump (FILE *f) const
1524 : {
1525 0 : fprintf (f, "Relation dump\n");
1526 0 : for (unsigned i = 0; i < m_relations.length (); i++)
1527 0 : if (BASIC_BLOCK_FOR_FN (cfun, i))
1528 : {
1529 0 : fprintf (f, "BB%d\n", i);
1530 0 : dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
1531 : }
1532 0 : }
1533 :
1534 : void
1535 0 : relation_oracle::debug () const
1536 : {
1537 0 : dump (stderr);
1538 0 : }
1539 :
1540 27459499 : path_oracle::path_oracle (relation_oracle *oracle)
1541 : {
1542 27459499 : set_root_oracle (oracle);
1543 27459499 : bitmap_obstack_initialize (&m_bitmaps);
1544 27459499 : obstack_init (&m_chain_obstack);
1545 :
1546 : // Initialize header records.
1547 27459499 : m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
1548 27459499 : m_equiv.m_bb = NULL;
1549 27459499 : m_equiv.m_next = NULL;
1550 27459499 : m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
1551 27459499 : m_relations.m_head = NULL;
1552 27459499 : m_killed_defs = BITMAP_ALLOC (&m_bitmaps);
1553 27459499 : }
1554 :
1555 54918998 : path_oracle::~path_oracle ()
1556 : {
1557 27459499 : obstack_free (&m_chain_obstack, NULL);
1558 27459499 : bitmap_obstack_release (&m_bitmaps);
1559 54918998 : }
1560 :
1561 : // Return the equiv set for SSA, and if there isn't one, check for equivs
1562 : // starting in block BB.
1563 :
1564 : const_bitmap
1565 123230184 : path_oracle::equiv_set (tree ssa, basic_block bb)
1566 : {
1567 : // Check the list first.
1568 123230184 : equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
1569 123230184 : if (ptr)
1570 66892259 : return ptr->m_names;
1571 :
1572 : // Otherwise defer to the root oracle.
1573 56337925 : if (m_root)
1574 50581322 : return m_root->equiv_set (ssa, bb);
1575 :
1576 : // Allocate a throw away bitmap if there isn't a root oracle.
1577 5756603 : bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
1578 5756603 : bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
1579 5756603 : return tmp;
1580 : }
1581 :
1582 : // Register an equivalence between SSA1 and SSA2 resolving unknowns from
1583 : // block BB. Return false if no new equivalence was added.
1584 :
1585 : bool
1586 7218314 : path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
1587 : {
1588 7218314 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
1589 7218314 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
1590 :
1591 : // Check if they are the same set, if so, we're done.
1592 7218314 : if (bitmap_equal_p (equiv_1, equiv_2))
1593 : return false;
1594 :
1595 : // Don't mess around, simply create a new record and insert it first.
1596 7205327 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
1597 7205327 : valid_equivs (b, equiv_1, bb);
1598 7205327 : valid_equivs (b, equiv_2, bb);
1599 :
1600 7205327 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1601 : sizeof (equiv_chain));
1602 7205327 : ptr->m_names = b;
1603 7205327 : ptr->m_bb = NULL;
1604 7205327 : ptr->m_next = m_equiv.m_next;
1605 7205327 : m_equiv.m_next = ptr;
1606 7205327 : bitmap_ior_into (m_equiv.m_names, b);
1607 7205327 : return true;
1608 : }
1609 :
1610 : // Register killing definition of an SSA_NAME.
1611 :
1612 : void
1613 52644135 : path_oracle::killing_def (tree ssa)
1614 : {
1615 52644135 : if (dump_file && (dump_flags & TDF_DETAILS))
1616 : {
1617 819 : fprintf (dump_file, " Registering killing_def (path_oracle) ");
1618 819 : print_generic_expr (dump_file, ssa, TDF_SLIM);
1619 819 : fprintf (dump_file, "\n");
1620 : }
1621 :
1622 52644135 : unsigned v = SSA_NAME_VERSION (ssa);
1623 :
1624 52644135 : bitmap_set_bit (m_killed_defs, v);
1625 52644135 : bitmap_set_bit (m_equiv.m_names, v);
1626 :
1627 : // Now add an equivalency with itself so we don't look to the root oracle.
1628 52644135 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
1629 52644135 : bitmap_set_bit (b, v);
1630 52644135 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1631 : sizeof (equiv_chain));
1632 52644135 : ptr->m_names = b;
1633 52644135 : ptr->m_bb = NULL;
1634 52644135 : ptr->m_next = m_equiv.m_next;
1635 52644135 : m_equiv.m_next = ptr;
1636 :
1637 : // Walk the relation list and remove SSA from any relations.
1638 52644135 : if (!bitmap_bit_p (m_relations.m_names, v))
1639 : return;
1640 :
1641 120147 : bitmap_clear_bit (m_relations.m_names, v);
1642 120147 : relation_chain **prev = &(m_relations.m_head);
1643 120147 : relation_chain *next = NULL;
1644 412569 : for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
1645 : {
1646 292422 : gcc_checking_assert (*prev == ptr);
1647 292422 : next = ptr->m_next;
1648 292422 : if (SSA_NAME_VERSION (ptr->op1 ()) == v
1649 292422 : || SSA_NAME_VERSION (ptr->op2 ()) == v)
1650 118954 : *prev = ptr->m_next;
1651 : else
1652 173468 : prev = &(ptr->m_next);
1653 : }
1654 : }
1655 :
1656 : // Register relation K between SSA1 and SSA2, resolving unknowns by
1657 : // querying from BB. Return false if no new relation is registered.
1658 :
1659 : bool
1660 25762415 : path_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
1661 : {
1662 : // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1663 : // and no other relation makes sense.
1664 25762415 : if (ssa1 == ssa2)
1665 : return false;
1666 :
1667 25718178 : relation_kind curr = query (bb, ssa1, ssa2);
1668 25718178 : if (curr != VREL_VARYING)
1669 1965261 : k = relation_intersect (curr, k);
1670 :
1671 25718178 : bool ret;
1672 25718178 : if (k == VREL_EQ)
1673 7218314 : ret = register_equiv (bb, ssa1, ssa2);
1674 : else
1675 : {
1676 18499864 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
1677 18499864 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
1678 18499864 : relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1679 : sizeof (relation_chain));
1680 18499864 : ptr->set_relation (k, ssa1, ssa2);
1681 18499864 : ptr->m_next = m_relations.m_head;
1682 18499864 : m_relations.m_head = ptr;
1683 18499864 : ret = true;
1684 : }
1685 :
1686 25718178 : if (ret && dump_file && (dump_flags & TDF_DETAILS))
1687 : {
1688 286 : value_relation vr (k, ssa1, ssa2);
1689 286 : fprintf (dump_file, " Registering value_relation (path_oracle) ");
1690 286 : vr.dump (dump_file);
1691 286 : fprintf (dump_file, " (root: bb%d)\n", bb->index);
1692 : }
1693 : return ret;
1694 : }
1695 :
1696 : // Query for a relationship between equiv set B1 and B2, resolving unknowns
1697 : // starting at block BB.
1698 :
1699 : relation_kind
1700 46264169 : path_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
1701 : {
1702 46264169 : if (bitmap_equal_p (b1, b2))
1703 : return VREL_EQ;
1704 :
1705 46264169 : relation_kind k = m_relations.find_relation (b1, b2);
1706 :
1707 : // Do not look at the root oracle for names that have been killed
1708 : // along the path.
1709 46264169 : if (bitmap_intersect_p (m_killed_defs, b1)
1710 46264169 : || bitmap_intersect_p (m_killed_defs, b2))
1711 34083757 : return k;
1712 :
1713 12180412 : if (k == VREL_VARYING && m_root)
1714 10099142 : k = m_root->query (bb, b1, b2);
1715 :
1716 : return k;
1717 : }
1718 :
1719 : // Query for a relationship between SSA1 and SSA2, resolving unknowns
1720 : // starting at block BB.
1721 :
1722 : relation_kind
1723 46869850 : path_oracle::query (basic_block bb, tree ssa1, tree ssa2)
1724 : {
1725 46869850 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1726 46869850 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1727 :
1728 46869850 : if (v1 == v2)
1729 : return VREL_EQ;
1730 :
1731 46778504 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
1732 46778504 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
1733 46778504 : if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
1734 : return VREL_EQ;
1735 :
1736 46264169 : return query (bb, equiv_1, equiv_2);
1737 : }
1738 :
1739 : // Reset any relations registered on this path. ORACLE is the root
1740 : // oracle to use.
1741 :
1742 : void
1743 22312082 : path_oracle::reset_path (relation_oracle *oracle)
1744 : {
1745 22312082 : set_root_oracle (oracle);
1746 22312082 : m_equiv.m_next = NULL;
1747 22312082 : bitmap_clear (m_equiv.m_names);
1748 22312082 : m_relations.m_head = NULL;
1749 22312082 : bitmap_clear (m_relations.m_names);
1750 22312082 : bitmap_clear (m_killed_defs);
1751 22312082 : }
1752 :
1753 : // Dump relation in basic block... Do nothing here.
1754 :
1755 : void
1756 0 : path_oracle::dump (FILE *, basic_block) const
1757 : {
1758 0 : }
1759 :
1760 : // Dump the relations and equivalencies found in the path.
1761 :
1762 : void
1763 0 : path_oracle::dump (FILE *f) const
1764 : {
1765 0 : equiv_chain *ptr = m_equiv.m_next;
1766 0 : relation_chain *ptr2 = m_relations.m_head;
1767 :
1768 0 : if (ptr || ptr2)
1769 0 : fprintf (f, "\npath_oracle:\n");
1770 :
1771 0 : for (; ptr; ptr = ptr->m_next)
1772 0 : ptr->dump (f);
1773 :
1774 0 : for (; ptr2; ptr2 = ptr2->m_next)
1775 : {
1776 0 : fprintf (f, "Relational : ");
1777 0 : ptr2->dump (f);
1778 0 : fprintf (f, "\n");
1779 : }
1780 0 : }
1781 :
1782 : // ------------------------------------------------------------------------
1783 : // EQUIV iterator. Although we have bitmap iterators, don't expose that it
1784 : // is currently a bitmap. Use an export iterator to hide future changes.
1785 :
1786 : // Construct a basic iterator over an equivalence bitmap.
1787 :
1788 49290793 : equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle,
1789 : basic_block bb, tree name,
1790 49290793 : bool full, bool partial)
1791 : {
1792 49290793 : m_name = name;
1793 49290793 : m_oracle = oracle;
1794 49290793 : m_pe = partial ? oracle->partial_equiv_set (name) : NULL;
1795 49290793 : m_bm = NULL;
1796 49290793 : if (full)
1797 49290793 : m_bm = oracle->equiv_set (name, bb);
1798 49290793 : if (!m_bm && m_pe)
1799 0 : m_bm = m_pe->members;
1800 49290793 : if (m_bm)
1801 49290792 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
1802 49290793 : }
1803 :
1804 : // Move to the next export bitmap spot.
1805 :
1806 : void
1807 64125550 : equiv_relation_iterator::next ()
1808 : {
1809 64125550 : bmp_iter_next (&m_bi, &m_y);
1810 64125550 : }
1811 :
1812 : // Fetch the name of the next export in the export list. Return NULL if
1813 : // iteration is done.
1814 :
1815 : tree
1816 58518782 : equiv_relation_iterator::get_name (relation_kind *rel)
1817 : {
1818 64125513 : if (!m_bm)
1819 : return NULL_TREE;
1820 :
1821 119023073 : while (bmp_iter_set (&m_bi, &m_y))
1822 : {
1823 : // Do not return self.
1824 64125550 : tree t = ssa_name (m_y);
1825 64125550 : if (t && t != m_name)
1826 : {
1827 9227989 : relation_kind k = VREL_EQ;
1828 9227989 : if (m_pe && m_bm == m_pe->members)
1829 : {
1830 7256706 : const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t);
1831 7256706 : if (equiv_pe && equiv_pe->members == m_pe->members)
1832 7256706 : k = pe_min (m_pe->code, equiv_pe->code);
1833 : else
1834 : k = VREL_VARYING;
1835 : }
1836 7256706 : if (relation_equiv_p (k))
1837 : {
1838 9227989 : if (rel)
1839 9227989 : *rel = k;
1840 9227989 : return t;
1841 : }
1842 : }
1843 54897561 : next ();
1844 : }
1845 :
1846 : // Process partial equivs after full equivs if both were requested.
1847 54897523 : if (m_pe && m_bm != m_pe->members)
1848 : {
1849 49290792 : m_bm = m_pe->members;
1850 49290792 : if (m_bm)
1851 : {
1852 : // Recursively call back to process First PE.
1853 5606731 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
1854 5606731 : return get_name (rel);
1855 : }
1856 : }
1857 : return NULL_TREE;
1858 : }
1859 :
1860 : #if CHECKING_P
1861 : #include "selftest.h"
1862 :
1863 : namespace selftest
1864 : {
1865 : void
1866 4 : relation_tests ()
1867 : {
1868 : // rr_*_table tables use unsigned char rather than relation_kind.
1869 4 : ASSERT_LT (VREL_LAST, UCHAR_MAX);
1870 : // Verify commutativity of relation_intersect and relation_union.
1871 36 : for (relation_kind r1 = VREL_VARYING; r1 < VREL_PE8;
1872 32 : r1 = relation_kind (r1 + 1))
1873 288 : for (relation_kind r2 = VREL_VARYING; r2 < VREL_PE8;
1874 256 : r2 = relation_kind (r2 + 1))
1875 : {
1876 256 : ASSERT_EQ (relation_intersect (r1, r2), relation_intersect (r2, r1));
1877 256 : ASSERT_EQ (relation_union (r1, r2), relation_union (r2, r1));
1878 : }
1879 4 : }
1880 :
1881 : } // namespace selftest
1882 :
1883 : #endif // CHECKING_P
|
