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 39444 : print_relation (FILE *f, relation_kind rel)
43 : {
44 39444 : fprintf (f, " %s ", kind_string[rel]);
45 39444 : }
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 19194545 : relation_swap (relation_kind r)
69 : {
70 19194545 : 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 101824762 : relation_intersect (relation_kind r1, relation_kind r2)
106 : {
107 101824762 : 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 92319288 : relation_union (relation_kind r1, relation_kind r2)
143 : {
144 92319288 : 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 8980368 : relation_transitive (relation_kind r1, relation_kind r2)
182 : {
183 8980368 : 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 2018605 : adjust_equivalence_range (vrange &range)
192 : {
193 2018605 : if (range.undefined_p () || !is_a<frange> (range))
194 1985016 : return;
195 :
196 33589 : frange fr = as_a<frange> (range);
197 : // If range includes 0 make sure both signs of zero are included.
198 33589 : if (fr.contains_p (dconst0) || fr.contains_p (dconstm0))
199 : {
200 17158 : frange zeros (range.type (), dconstm0, dconst0);
201 17158 : range.union_ (zeros);
202 17158 : }
203 33589 : }
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 23641951 : relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
210 : {
211 23641951 : unsigned i;
212 23641951 : bitmap_iterator bi;
213 49367935 : EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
214 : {
215 25725984 : tree ssa = ssa_name (i);
216 51451968 : if (ssa && !SSA_NAME_IN_FREE_LIST (ssa))
217 : {
218 25725984 : const_bitmap ssa_equiv = equiv_set (ssa, bb);
219 25725984 : if (ssa_equiv == equivs)
220 25444685 : bitmap_set_bit (b, i);
221 : }
222 : }
223 23641951 : }
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 114549164 : relation_oracle::query (gimple *s, tree ssa1, tree ssa2)
231 : {
232 114549164 : if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
233 : return VREL_VARYING;
234 42948849 : 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 50981802 : relation_oracle::query (edge e, tree ssa1, tree ssa2)
243 : {
244 50981802 : basic_block bb;
245 50981802 : 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 37648809 : if (!single_pred_p (e->dest))
252 35948706 : bb = e->src;
253 : else
254 : bb = e->dest;
255 :
256 37648809 : 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 207632303 : equiv_chain::find (unsigned ssa)
273 : {
274 207632303 : 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 207632303 : if (bitmap_bit_p (m_names, ssa))
278 : {
279 242996066 : for (ptr = m_next; ptr; ptr = ptr->m_next)
280 242996066 : if (bitmap_bit_p (ptr->m_names, ssa))
281 : break;
282 : }
283 207632303 : return ptr;
284 : }
285 :
286 : // Dump the names in this equivalence set.
287 :
288 : void
289 12 : equiv_chain::dump (FILE *f) const
290 : {
291 12 : bitmap_iterator bi;
292 12 : unsigned i;
293 :
294 12 : if (!m_names || bitmap_empty_p (m_names))
295 1 : return;
296 11 : fprintf (f, "Equivalence set : [");
297 11 : unsigned c = 0;
298 29 : EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
299 : {
300 18 : if (ssa_name (i))
301 : {
302 18 : if (c++)
303 7 : fprintf (f, ", ");
304 18 : print_generic_expr (f, ssa_name (i), TDF_SLIM);
305 : }
306 : }
307 11 : fprintf (f, "]\n");
308 : }
309 :
310 : // Instantiate an equivalency oracle.
311 :
312 27374017 : equiv_oracle::equiv_oracle ()
313 : {
314 27374017 : bitmap_obstack_initialize (&m_bitmaps);
315 27374017 : m_equiv.create (0);
316 27374017 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
317 27374017 : m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
318 27374017 : bitmap_tree_view (m_equiv_set);
319 27374017 : obstack_init (&m_chain_obstack);
320 27374017 : m_name_info.create (0);
321 54748034 : m_name_info.safe_grow_cleared (num_ssa_names + 1);
322 27374017 : m_partial.create (0);
323 54748034 : 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 27374017 : m_lhs_equiv_set_p = BITMAP_ALLOC (&m_bitmaps);
327 27374017 : bitmap_tree_view (m_lhs_equiv_set_p);
328 27374017 : }
329 :
330 : // Destruct an equivalency oracle.
331 :
332 27374017 : equiv_oracle::~equiv_oracle ()
333 : {
334 27374017 : m_partial.release ();
335 27374017 : m_name_info.release ();
336 27374017 : obstack_free (&m_chain_obstack, NULL);
337 27374017 : m_equiv.release ();
338 27374017 : bitmap_obstack_release (&m_bitmaps);
339 27374017 : }
340 :
341 : // Add a partial equivalence R between OP1 and OP2. Return false if no
342 : // new relation is added.
343 :
344 : bool
345 10203194 : equiv_oracle::add_partial_equiv (relation_kind r, tree op1, tree op2)
346 : {
347 10203194 : int v1 = SSA_NAME_VERSION (op1);
348 10203194 : int v2 = SSA_NAME_VERSION (op2);
349 10203194 : int prec2 = TYPE_PRECISION (TREE_TYPE (op2));
350 10203194 : int bits = pe_to_bits (r);
351 10203194 : gcc_checking_assert (bits && prec2 >= bits);
352 :
353 20406388 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
354 462 : m_partial.safe_grow_cleared (num_ssa_names + 1);
355 20406388 : gcc_checking_assert (v1 < (int)m_partial.length ()
356 : && v2 < (int)m_partial.length ());
357 :
358 10203194 : pe_slice &pe1 = m_partial[v1];
359 10203194 : pe_slice &pe2 = m_partial[v2];
360 :
361 10203194 : 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 202 : if (pe2.members)
367 : return false;
368 : // If there are no uses of op2, do not register.
369 179 : 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 179 : pe2.code = pe_min (r, pe1.code);
374 179 : pe2.ssa_base = op2;
375 179 : pe2.members = pe1.members;
376 179 : bitmap_iterator bi;
377 179 : unsigned x;
378 541 : EXECUTE_IF_SET_IN_BITMAP (pe1.members, 0, x, bi)
379 : {
380 362 : m_partial[x].ssa_base = op2;
381 362 : m_partial[x].code = pe_min (m_partial[x].code, pe2.code);
382 : }
383 179 : bitmap_set_bit (pe1.members, v2);
384 179 : return true;
385 : }
386 10202992 : if (pe2.members)
387 : {
388 : // If there are no uses of op1, do not register.
389 734148 : if (has_zero_uses (op1))
390 : return false;
391 725396 : 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 725396 : pe1.code = pe_min (r, pe2.code);
395 725396 : pe1.members = pe2.members;
396 725396 : bitmap_set_bit (pe1.members, v1);
397 : }
398 : else
399 : {
400 : // If there are no uses of either operand, do not register.
401 9468844 : 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 9384813 : pe2.code = bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2)));
405 9384813 : if (pe2.code == VREL_VARYING)
406 : return false;
407 9330811 : pe2.ssa_base = op2;
408 9330811 : pe2.members = BITMAP_ALLOC (&m_bitmaps);
409 9330811 : bitmap_set_bit (pe2.members, v2);
410 9330811 : pe1.ssa_base = op2;
411 9330811 : pe1.code = r;
412 9330811 : pe1.members = pe2.members;
413 9330811 : 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 60913519 : equiv_oracle::partial_equiv_set (tree name)
423 : {
424 60913519 : int v = SSA_NAME_VERSION (name);
425 121827038 : if (v >= (int)m_partial.length ())
426 : return NULL;
427 60913519 : 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 103110621 : equiv_oracle::partial_equiv (tree ssa1, tree ssa2, tree *base) const
436 : {
437 103110621 : int v1 = SSA_NAME_VERSION (ssa1);
438 103110621 : int v2 = SSA_NAME_VERSION (ssa2);
439 :
440 206221242 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
441 : return VREL_VARYING;
442 :
443 103110549 : const pe_slice &pe1 = m_partial[v1];
444 103110549 : const pe_slice &pe2 = m_partial[v2];
445 103110549 : if (pe1.members && pe2.members == pe1.members)
446 : {
447 1226750 : if (base)
448 0 : *base = pe1.ssa_base;
449 1226750 : return pe_min (pe1.code, pe2.code);
450 : }
451 : return VREL_VARYING;
452 : }
453 :
454 : void
455 18049187 : equiv_oracle::register_equiv_block (unsigned v, unsigned bbi)
456 : {
457 18049187 : if (v >= m_name_info.length ())
458 50 : m_name_info.safe_grow_cleared (num_ssa_names + 1);
459 :
460 18049187 : if (!m_name_info[v].m_block_list)
461 7476635 : m_name_info[v].m_block_list = BITMAP_ALLOC (&m_bitmaps);
462 :
463 18049187 : bitmap_set_bit (m_name_info[v].m_block_list, bbi);
464 18049187 : }
465 :
466 : void
467 12985400 : equiv_oracle::register_equiv_block (const_bitmap names, basic_block bb)
468 : {
469 12985400 : bitmap_iterator bi;
470 12985400 : unsigned v;
471 :
472 31018273 : EXECUTE_IF_SET_IN_BITMAP (names, 0, v, bi)
473 18032873 : register_equiv_block (v, bb->index);
474 12985400 : }
475 :
476 : // Find and return the equivalency set for SSA along the dominators of BB.
477 : // This is the external API.
478 :
479 : const_bitmap
480 171160461 : equiv_oracle::equiv_set (tree ssa, basic_block bb)
481 : {
482 : // Search the dominator tree for an equivalency.
483 171160461 : equiv_chain *equiv = find_equiv_dom (ssa, bb);
484 171160461 : if (equiv)
485 19178621 : return equiv->m_names;
486 :
487 : // Otherwise return a cached equiv set containing just this SSA.
488 151981840 : unsigned v = SSA_NAME_VERSION (ssa);
489 151981840 : if (v >= m_name_info.length ())
490 224 : m_name_info.safe_grow_cleared (num_ssa_names + 1);
491 :
492 151981840 : if (!m_name_info[v].m_self_equiv)
493 : {
494 36947696 : m_name_info[v].m_self_equiv = BITMAP_ALLOC (&m_bitmaps);
495 36947696 : bitmap_set_bit (m_name_info[v].m_self_equiv, v);
496 : }
497 151981840 : return m_name_info[v].m_self_equiv;
498 : }
499 :
500 : // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
501 :
502 : relation_kind
503 0 : equiv_oracle::query (basic_block bb, tree ssa1, tree ssa2)
504 : {
505 : // If the 2 ssa names share the same equiv set, they are equal.
506 0 : if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb))
507 : return VREL_EQ;
508 :
509 : // Check if there is a partial equivalence.
510 0 : return partial_equiv (ssa1, ssa2);
511 : }
512 :
513 : // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
514 :
515 : relation_kind
516 0 : equiv_oracle::query (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1,
517 : const_bitmap e2)
518 : {
519 : // If the 2 ssa names share the same equiv set, they are equal.
520 0 : if (bitmap_equal_p (e1, e2))
521 0 : return VREL_EQ;
522 : return VREL_VARYING;
523 : }
524 :
525 : // If SSA has an equivalence in block BB, find and return it.
526 : // Otherwise return NULL.
527 :
528 : equiv_chain *
529 142055521 : equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
530 : {
531 284111042 : if (bb >= (int)m_equiv.length () || !m_equiv[bb])
532 : return NULL;
533 :
534 59411325 : return m_equiv[bb]->find (ssa);
535 : }
536 :
537 : // Starting at block BB, walk the dominator chain looking for the nearest
538 : // equivalence set containing NAME.
539 :
540 : equiv_chain *
541 186843957 : equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
542 : {
543 186843957 : unsigned v = SSA_NAME_VERSION (name);
544 : // Short circuit looking for names which have no equivalences.
545 : // Saves time looking for something which does not exist.
546 186843957 : if (!bitmap_bit_p (m_equiv_set, v))
547 : return NULL;
548 :
549 : // NAME has at least once equivalence set, check to see if it has one along
550 : // the dominator tree.
551 144245494 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
552 : {
553 142055521 : equiv_chain *ptr = find_equiv_block (v, bb->index);
554 142055521 : if (ptr)
555 : return ptr;
556 : }
557 : return NULL;
558 : }
559 :
560 : // Register equivalence between ssa_name V and set EQUIV in block BB,
561 :
562 : bitmap
563 77277 : equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
564 : {
565 : // V will have an equivalency now.
566 77277 : bitmap_set_bit (m_equiv_set, v);
567 :
568 : // If that equiv chain is in this block, simply use it.
569 77277 : if (equiv->m_bb == bb)
570 : {
571 16314 : bitmap_set_bit (equiv->m_names, v);
572 16314 : bitmap_set_bit (m_equiv[bb->index]->m_names, v);
573 : // Add BB to V.
574 16314 : register_equiv_block (v, bb->index);
575 16314 : return NULL;
576 : }
577 :
578 : // Otherwise create an equivalence for this block which is a copy
579 : // of equiv, the add V to the set.
580 60963 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
581 60963 : valid_equivs (b, equiv->m_names, bb);
582 60963 : bitmap_set_bit (b, v);
583 : // Add BB to the all the equiv names.
584 60963 : register_equiv_block (b, bb);
585 60963 : return b;
586 : }
587 :
588 : // Register equivalence between set equiv_1 and equiv_2 in block BB.
589 : // Return NULL if either name can be merged with the other. Otherwise
590 : // return a pointer to the combined bitmap of names. This allows the
591 : // caller to do any setup required for a new element.
592 :
593 : bitmap
594 4057150 : equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
595 : equiv_chain *equiv_2)
596 : {
597 : // If equiv_1 is already in BB, use it as the combined set.
598 4057150 : if (equiv_1->m_bb == bb)
599 : {
600 2265128 : valid_equivs (equiv_1->m_names, equiv_2->m_names, bb);
601 : // Its hard to delete from a single linked list, so
602 : // just clear the second one.
603 2265128 : if (equiv_2->m_bb == bb)
604 384218 : bitmap_clear (equiv_2->m_names);
605 : else
606 : {
607 : // Ensure the new names are in the summary for BB.
608 1880910 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
609 : // Add BB to the names in equiv2.
610 1880910 : register_equiv_block (equiv_2->m_names, bb);
611 : }
612 : return NULL;
613 : }
614 : // If equiv_2 is in BB, use it for the combined set.
615 1792022 : if (equiv_2->m_bb == bb)
616 : {
617 2516 : valid_equivs (equiv_2->m_names, equiv_1->m_names, bb);
618 : // Ensure the new names are in the summary.
619 2516 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
620 : // Add BB to the names in equiv1.
621 2516 : register_equiv_block (equiv_1->m_names, bb);
622 2516 : return NULL;
623 : }
624 :
625 : // At this point, neither equivalence is from this block.
626 1789506 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
627 1789506 : valid_equivs (b, equiv_1->m_names, bb);
628 1789506 : valid_equivs (b, equiv_2->m_names, bb);
629 : // Add BB to the all the equiv names.
630 1789506 : register_equiv_block (b, bb);
631 1789506 : return b;
632 : }
633 :
634 : // Create an equivalency set containing only SSA in its definition block.
635 : // This is done the first time SSA is registered in an equivalency and blocks
636 : // any DOM searches past the definition.
637 :
638 : void
639 7476635 : equiv_oracle::register_initial_def (tree ssa)
640 : {
641 7476635 : if (SSA_NAME_IS_DEFAULT_DEF (ssa))
642 : return;
643 7390987 : basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
644 :
645 : // If defining stmt is not in the IL, simply return.
646 7390987 : if (!bb)
647 : return;
648 7390986 : gcc_checking_assert (!find_equiv_dom (ssa, bb));
649 :
650 7390986 : unsigned v = SSA_NAME_VERSION (ssa);
651 7390986 : bitmap_set_bit (m_equiv_set, v);
652 7390986 : bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps);
653 7390986 : bitmap_set_bit (equiv_set, v);
654 7390986 : add_equiv_to_block (bb, equiv_set);
655 : }
656 :
657 : // Clear the equivalence lists and partial equivalencs for NAME.
658 :
659 : void
660 1157 : equiv_oracle::clear (tree name)
661 : {
662 1157 : unsigned v = SSA_NAME_VERSION (name);
663 : // Remove NAME from any blocks it is an equivalence in.
664 1157 : if (bitmap_bit_p (m_equiv_set, v))
665 : {
666 785 : gcc_checking_assert (m_name_info[v].m_block_list);
667 785 : bitmap_iterator bi;
668 785 : unsigned bbi;
669 :
670 1570 : EXECUTE_IF_SET_IN_BITMAP (m_name_info[v].m_block_list, 0, bbi, bi)
671 : {
672 785 : if (bbi >= m_equiv.length ())
673 : break;
674 785 : if (!m_equiv[bbi])
675 0 : continue;
676 785 : equiv_chain *ptr = m_equiv[bbi]->find (v);
677 785 : if (ptr)
678 : {
679 785 : bitmap_clear_bit (ptr->m_names, v);
680 785 : bitmap_clear_bit (m_equiv[bbi]->m_names, v);
681 : }
682 : }
683 785 : bitmap_clear_bit (m_equiv_set, v);
684 785 : bitmap_clear (m_name_info[v].m_block_list);
685 : }
686 : // Eliminate any partial equivs.
687 1157 : if (v < m_partial.length ())
688 1157 : m_partial[v].members = NULL;
689 1157 : }
690 :
691 :
692 : // Register an equivalence between SSA1 and SSA2 in block BB.
693 : // The equivalence oracle maintains a vector of equivalencies indexed by basic
694 : // block. When an equivalence between SSA1 and SSA2 is registered in block BB,
695 : // a query is made as to what equivalences both names have already, and
696 : // any preexisting equivalences are merged to create a single equivalence
697 : // containing all the ssa_names in this basic block.
698 : // Return false if no new relation is added.
699 :
700 : bool
701 14349449 : equiv_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
702 : {
703 : // Process partial equivalencies.
704 14349449 : if (relation_partial_equiv_p (k))
705 10203194 : return add_partial_equiv (k, ssa1, ssa2);
706 :
707 : // Only handle equality relations.
708 4146255 : if (k != VREL_EQ)
709 : return false;
710 :
711 4146255 : unsigned v1 = SSA_NAME_VERSION (ssa1);
712 4146255 : unsigned v2 = SSA_NAME_VERSION (ssa2);
713 :
714 : // If this is the first time an ssa_name has an equivalency registered
715 : // create a self-equivalency record in the def block.
716 4146255 : if (!bitmap_bit_p (m_equiv_set, v1))
717 3979148 : register_initial_def (ssa1);
718 4146255 : if (!bitmap_bit_p (m_equiv_set, v2))
719 3497487 : register_initial_def (ssa2);
720 :
721 4146255 : equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
722 4146255 : equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
723 :
724 : // Check if they are the same set
725 4146255 : if (equiv_1 && equiv_1 == equiv_2)
726 : return false;
727 :
728 4144477 : bitmap equiv_set;
729 :
730 : // Case where we have 2 SSA_NAMEs that are not in any set.
731 4144477 : if (!equiv_1 && !equiv_2)
732 : {
733 10050 : bitmap_set_bit (m_equiv_set, v1);
734 10050 : bitmap_set_bit (m_equiv_set, v2);
735 :
736 10050 : equiv_set = BITMAP_ALLOC (&m_bitmaps);
737 10050 : bitmap_set_bit (equiv_set, v1);
738 10050 : bitmap_set_bit (equiv_set, v2);
739 : }
740 4134427 : else if (!equiv_1 && equiv_2)
741 23553 : equiv_set = register_equiv (bb, v1, equiv_2);
742 4110874 : else if (equiv_1 && !equiv_2)
743 53724 : equiv_set = register_equiv (bb, v2, equiv_1);
744 : else
745 4057150 : equiv_set = register_equiv (bb, equiv_1, equiv_2);
746 :
747 : // A non-null return is a bitmap that is to be added to the current
748 : // block as a new equivalence.
749 4144477 : if (!equiv_set)
750 : return false;
751 :
752 1860519 : add_equiv_to_block (bb, equiv_set);
753 1860519 : return true;
754 : }
755 :
756 : // Add an equivalency record in block BB containing bitmap EQUIV_SET.
757 : // Note the internal caller is responsible for allocating EQUIV_SET properly.
758 :
759 : void
760 9251505 : equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
761 : {
762 9251505 : equiv_chain *ptr;
763 :
764 : // Check if this is the first time a block has an equivalence added.
765 : // and create a header block. And set the summary for this block.
766 9251505 : limit_check (bb);
767 9251505 : if (!m_equiv[bb->index])
768 : {
769 5883010 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
770 : sizeof (equiv_chain));
771 5883010 : ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
772 5883010 : bitmap_copy (ptr->m_names, equiv_set);
773 5883010 : ptr->m_bb = bb;
774 5883010 : ptr->m_next = NULL;
775 5883010 : m_equiv[bb->index] = ptr;
776 : }
777 :
778 : // Now create the element for this equiv set and initialize it.
779 9251505 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
780 9251505 : ptr->m_names = equiv_set;
781 9251505 : ptr->m_bb = bb;
782 18503010 : gcc_checking_assert (bb->index < (int)m_equiv.length ());
783 9251505 : ptr->m_next = m_equiv[bb->index]->m_next;
784 9251505 : m_equiv[bb->index]->m_next = ptr;
785 9251505 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
786 : // Add BB to the equiv set.
787 9251505 : register_equiv_block (equiv_set, bb);
788 9251505 : }
789 :
790 : // Make sure the BB vector is big enough and grow it if needed.
791 :
792 : void
793 9251505 : equiv_oracle::limit_check (basic_block bb)
794 : {
795 9251505 : int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
796 18503010 : if (i >= (int)m_equiv.length ())
797 47 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
798 9251505 : }
799 :
800 : // Dump the equivalence sets in BB to file F.
801 :
802 : void
803 257 : equiv_oracle::dump (FILE *f, basic_block bb) const
804 : {
805 514 : if (bb->index >= (int)m_equiv.length ())
806 : return;
807 : // Process equivalences.
808 257 : if (m_equiv[bb->index])
809 : {
810 10 : equiv_chain *ptr = m_equiv[bb->index]->m_next;
811 22 : for (; ptr; ptr = ptr->m_next)
812 12 : ptr->dump (f);
813 : }
814 : // Look for partial equivalences defined in this block..
815 12764 : for (unsigned i = 0; i < num_ssa_names; i++)
816 : {
817 12507 : tree name = ssa_name (i);
818 17757 : if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name))
819 7257 : continue;
820 5250 : if (i >= m_partial.length ())
821 : break;
822 5250 : tree base = m_partial[i].ssa_base;
823 5250 : if (base && name != base && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb)
824 : {
825 42 : relation_kind k = partial_equiv (name, base);
826 42 : if (k != VREL_VARYING)
827 : {
828 42 : value_relation vr (k, name, base);
829 42 : fprintf (f, "Partial equiv ");
830 42 : vr.dump (f);
831 42 : fputc ('\n',f);
832 : }
833 : }
834 : }
835 : }
836 :
837 : // Dump all equivalence sets known to the oracle.
838 :
839 : void
840 0 : equiv_oracle::dump (FILE *f) const
841 : {
842 0 : fprintf (f, "Equivalency dump\n");
843 0 : for (unsigned i = 0; i < m_equiv.length (); i++)
844 0 : if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
845 : {
846 0 : fprintf (f, "BB%d\n", i);
847 0 : dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
848 : }
849 0 : }
850 :
851 :
852 : // --------------------------------------------------------------------------
853 :
854 : // Adjust the relation by Swapping the operands and relation.
855 :
856 : void
857 0 : value_relation::swap ()
858 : {
859 0 : related = relation_swap (related);
860 0 : tree tmp = name1;
861 0 : name1 = name2;
862 0 : name2 = tmp;
863 0 : }
864 :
865 : // Perform an intersection between 2 relations. *this &&= p.
866 : // Return false if the relations cannot be intersected.
867 :
868 : bool
869 2435132 : value_relation::intersect (value_relation &p)
870 : {
871 : // Save previous value
872 2435132 : relation_kind old = related;
873 :
874 2435132 : if (p.op1 () == op1 () && p.op2 () == op2 ())
875 2434813 : related = relation_intersect (kind (), p.kind ());
876 319 : else if (p.op2 () == op1 () && p.op1 () == op2 ())
877 319 : related = relation_intersect (kind (), relation_swap (p.kind ()));
878 : else
879 : return false;
880 :
881 2435132 : return old != related;
882 : }
883 :
884 : // Perform a union between 2 relations. *this ||= p.
885 :
886 : bool
887 0 : value_relation::union_ (value_relation &p)
888 : {
889 : // Save previous value
890 0 : relation_kind old = related;
891 :
892 0 : if (p.op1 () == op1 () && p.op2 () == op2 ())
893 0 : related = relation_union (kind(), p.kind());
894 0 : else if (p.op2 () == op1 () && p.op1 () == op2 ())
895 0 : related = relation_union (kind(), relation_swap (p.kind ()));
896 : else
897 : return false;
898 :
899 0 : return old != related;
900 : }
901 :
902 : // Identify and apply any transitive relations between REL
903 : // and THIS. Return true if there was a transformation.
904 :
905 : bool
906 13901279 : value_relation::apply_transitive (const value_relation &rel)
907 : {
908 13901279 : relation_kind k = VREL_VARYING;
909 :
910 : // Identify any common operand, and normalize the relations to
911 : // the form : A < B B < C produces A < C
912 13901279 : if (rel.op1 () == name2)
913 : {
914 : // A < B B < C
915 2177974 : if (rel.op2 () == name1)
916 : return false;
917 2109887 : k = relation_transitive (kind (), rel.kind ());
918 2109887 : if (k != VREL_VARYING)
919 : {
920 853695 : related = k;
921 853695 : name2 = rel.op2 ();
922 853695 : return true;
923 : }
924 : }
925 11723305 : else if (rel.op1 () == name1)
926 : {
927 : // B > A B < C
928 6714997 : if (rel.op2 () == name2)
929 : return false;
930 1862173 : k = relation_transitive (relation_swap (kind ()), rel.kind ());
931 1862173 : if (k != VREL_VARYING)
932 : {
933 473359 : related = k;
934 473359 : name1 = name2;
935 473359 : name2 = rel.op2 ();
936 473359 : return true;
937 : }
938 : }
939 5008308 : else if (rel.op2 () == name2)
940 : {
941 : // A < B C > B
942 4388017 : if (rel.op1 () == name1)
943 : return false;
944 4388017 : k = relation_transitive (kind (), relation_swap (rel.kind ()));
945 4388017 : if (k != VREL_VARYING)
946 : {
947 530271 : related = k;
948 530271 : name2 = rel.op1 ();
949 530271 : return true;
950 : }
951 : }
952 620291 : else if (rel.op2 () == name1)
953 : {
954 : // B > A C > B
955 620291 : if (rel.op1 () == name2)
956 : return false;
957 620291 : k = relation_transitive (relation_swap (kind ()),
958 : relation_swap (rel.kind ()));
959 620291 : if (k != VREL_VARYING)
960 : {
961 238177 : related = k;
962 238177 : name1 = name2;
963 238177 : name2 = rel.op1 ();
964 238177 : return true;
965 : }
966 : }
967 : return false;
968 : }
969 :
970 : // Create a trio from this value relation given LHS, OP1 and OP2.
971 :
972 : relation_trio
973 53558206 : value_relation::create_trio (tree lhs, tree op1, tree op2)
974 : {
975 53558206 : relation_kind lhs_1;
976 53558206 : if (lhs == name1 && op1 == name2)
977 65916 : lhs_1 = related;
978 53492290 : else if (lhs == name2 && op1 == name1)
979 176921 : lhs_1 = relation_swap (related);
980 : else
981 : lhs_1 = VREL_VARYING;
982 :
983 53558206 : relation_kind lhs_2;
984 53558206 : if (lhs == name1 && op2 == name2)
985 55143 : lhs_2 = related;
986 53503063 : else if (lhs == name2 && op2 == name1)
987 133016 : lhs_2 = relation_swap (related);
988 : else
989 : lhs_2 = VREL_VARYING;
990 :
991 53558206 : relation_kind op_op;
992 53558206 : if (op1 == name1 && op2 == name2)
993 37807795 : op_op = related;
994 15750411 : else if (op1 == name2 && op2 == name1)
995 0 : op_op = relation_swap (related);
996 15750411 : else if (op1 == op2)
997 : op_op = VREL_EQ;
998 : else
999 15734678 : op_op = VREL_VARYING;
1000 :
1001 53558206 : return relation_trio (lhs_1, lhs_2, op_op);
1002 : }
1003 :
1004 : // Dump the relation to file F.
1005 :
1006 : void
1007 39294 : value_relation::dump (FILE *f) const
1008 : {
1009 39294 : if (!name1 || !name2)
1010 : {
1011 0 : fprintf (f, "no relation registered");
1012 0 : return;
1013 : }
1014 39294 : fputc ('(', f);
1015 39294 : print_generic_expr (f, op1 (), TDF_SLIM);
1016 39294 : print_relation (f, kind ());
1017 39294 : print_generic_expr (f, op2 (), TDF_SLIM);
1018 39294 : fputc(')', f);
1019 : }
1020 :
1021 : // This container is used to link relations in a chain.
1022 :
1023 : class relation_chain : public value_relation
1024 : {
1025 : public:
1026 : relation_chain *m_next;
1027 : };
1028 :
1029 : // Given relation record PTR in block BB, return the next relation in the
1030 : // list. If PTR is NULL, retrieve the first relation in BB.
1031 : // If NAME is sprecified, return only relations which include NAME.
1032 : // Return NULL when there are no relations left.
1033 :
1034 : relation_chain *
1035 84 : dom_oracle::next_relation (basic_block bb, relation_chain *ptr,
1036 : tree name) const
1037 : {
1038 84 : relation_chain *p;
1039 : // No value_relation pointer is used to initialize the iterator.
1040 84 : if (!ptr)
1041 : {
1042 37 : int bbi = bb->index;
1043 74 : if (bbi >= (int)m_relations.length())
1044 : return NULL;
1045 : else
1046 37 : p = m_relations[bbi].m_head;
1047 : }
1048 : else
1049 47 : p = ptr->m_next;
1050 :
1051 84 : if (name)
1052 0 : for ( ; p; p = p->m_next)
1053 0 : if (p->op1 () == name || p->op2 () == name)
1054 : break;
1055 : return p;
1056 : }
1057 :
1058 : // Instantiate a block relation iterator to iterate over the relations
1059 : // on exit from block BB in ORACLE. Limit this to relations involving NAME
1060 : // if specified. Return the first such relation in VR if there is one.
1061 :
1062 37 : block_relation_iterator::block_relation_iterator (const relation_oracle *oracle,
1063 : basic_block bb,
1064 : value_relation &vr,
1065 : tree name)
1066 : {
1067 37 : m_oracle = oracle;
1068 37 : m_bb = bb;
1069 37 : m_name = name;
1070 37 : m_ptr = oracle->next_relation (bb, NULL, m_name);
1071 37 : if (m_ptr)
1072 : {
1073 37 : m_done = false;
1074 37 : vr = *m_ptr;
1075 : }
1076 : else
1077 0 : m_done = true;
1078 37 : }
1079 :
1080 : // Retrieve the next relation from the iterator and return it in VR.
1081 :
1082 : void
1083 47 : block_relation_iterator::get_next_relation (value_relation &vr)
1084 : {
1085 47 : m_ptr = m_oracle->next_relation (m_bb, m_ptr, m_name);
1086 47 : if (m_ptr)
1087 : {
1088 10 : vr = *m_ptr;
1089 10 : if (m_name)
1090 : {
1091 0 : if (vr.op1 () != m_name)
1092 : {
1093 0 : gcc_checking_assert (vr.op2 () == m_name);
1094 0 : vr.swap ();
1095 : }
1096 : }
1097 : }
1098 : else
1099 37 : m_done = true;
1100 47 : }
1101 :
1102 : // ------------------------------------------------------------------------
1103 :
1104 : // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
1105 : // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1106 :
1107 : relation_kind
1108 461822221 : relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
1109 : {
1110 461822221 : if (!m_names)
1111 : return VREL_VARYING;
1112 :
1113 : // If both b1 and b2 aren't referenced in this block, cant be a relation
1114 223533761 : if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
1115 : return VREL_VARYING;
1116 :
1117 : // Search for the first relation that contains BOTH an element from B1
1118 : // and B2, and return that relation.
1119 17459075 : for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
1120 : {
1121 15024049 : unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1122 15024049 : unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1123 15024049 : if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
1124 2953546 : return ptr->kind ();
1125 12070503 : if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
1126 159401 : return relation_swap (ptr->kind ());
1127 : }
1128 :
1129 : return VREL_VARYING;
1130 : }
1131 :
1132 : // Instantiate a relation oracle.
1133 :
1134 27374017 : dom_oracle::dom_oracle (bool do_trans_p)
1135 : {
1136 27374017 : m_do_trans_p = do_trans_p;
1137 27374017 : m_relations.create (0);
1138 27374017 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1139 27374017 : m_relation_set = BITMAP_ALLOC (&m_bitmaps);
1140 27374017 : m_block_list.create (0);
1141 54748034 : m_block_list.safe_grow_cleared (num_ssa_names + 1);
1142 27374017 : m_tmp = BITMAP_ALLOC (&m_bitmaps);
1143 27374017 : m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
1144 27374017 : }
1145 :
1146 : // Destruct a relation oracle.
1147 :
1148 54748034 : dom_oracle::~dom_oracle ()
1149 : {
1150 27374017 : m_block_list.release ();
1151 27374017 : m_relations.release ();
1152 54748034 : }
1153 :
1154 : // Remove any relations with NAME from this list.
1155 :
1156 : void
1157 91 : relation_chain_head::clear (tree name)
1158 : {
1159 91 : unsigned v = SSA_NAME_VERSION (name);
1160 91 : if (!m_names || !bitmap_bit_p (m_names, v))
1161 : return;
1162 :
1163 91 : relation_chain *ptr, *last = NULL;;
1164 :
1165 146 : for (ptr = m_head; ptr; ptr = ptr->m_next)
1166 : {
1167 55 : tree op1 = ptr->op1 ();
1168 55 : tree op2 = ptr->op2 ();
1169 : // Delink any elements with NAME.
1170 55 : if (op1 == name || op2 == name)
1171 : {
1172 55 : if (!last)
1173 55 : m_head = ptr->m_next;
1174 : else
1175 0 : last->m_next = ptr->m_next;
1176 55 : m_num_relations--;
1177 : }
1178 : else
1179 : last = ptr;
1180 : }
1181 : // And remove name from the possible relations in this block bitfield.
1182 91 : bitmap_clear_bit (m_names, v);
1183 : }
1184 :
1185 : // Remove any relations involving NAME from the DOM oracle
1186 :
1187 : void
1188 1157 : dom_oracle::clear (tree name)
1189 : {
1190 1157 : equiv_oracle::clear (name);
1191 1157 : unsigned v = SSA_NAME_VERSION (name);
1192 1157 : if (bitmap_bit_p (m_relation_set, v))
1193 : {
1194 91 : gcc_checking_assert (m_block_list[v]);
1195 91 : bitmap_iterator bi;
1196 91 : unsigned bbi;
1197 :
1198 182 : EXECUTE_IF_SET_IN_BITMAP (m_block_list[v], 0, bbi, bi)
1199 : {
1200 91 : if (bbi >= m_relations.length())
1201 : break;
1202 91 : m_relations[bbi].clear (name);
1203 : }
1204 91 : bitmap_clear_bit (m_relation_set, v);
1205 91 : bitmap_clear (m_block_list[v]);
1206 : }
1207 1157 : }
1208 :
1209 : // Register relation K between ssa_name OP1 and OP2 on STMT.
1210 : // Return false if no new relation is added.
1211 :
1212 : bool
1213 31168891 : relation_oracle::record (gimple *stmt, relation_kind k, tree op1, tree op2)
1214 : {
1215 31168891 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1216 31168891 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1217 31168891 : gcc_checking_assert (stmt && gimple_bb (stmt));
1218 :
1219 : // Don't register lack of a relation.
1220 31168891 : if (k == VREL_VARYING)
1221 : return false;
1222 :
1223 : // If an equivalence is being added between a PHI and one of its arguments
1224 : // make sure that that argument is not defined in the same block.
1225 : // This can happen along back edges and the equivalence will not be
1226 : // applicable as it would require a use before def.
1227 31168891 : if (k == VREL_EQ && is_a<gphi *> (stmt))
1228 : {
1229 1875046 : tree phi_def = gimple_phi_result (stmt);
1230 1875046 : gcc_checking_assert (phi_def == op1 || phi_def == op2);
1231 1875046 : tree arg = op2;
1232 1875046 : if (phi_def == op2)
1233 0 : arg = op1;
1234 1875046 : if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
1235 : return false;
1236 : }
1237 :
1238 : // If the LHS of a statement has already been processed and an equivalence
1239 : // registered, do not register another one. See PR 124809.
1240 74819868 : if (m_lhs_equiv_set_p && relation_equiv_p (k)
1241 44150904 : && gimple_get_lhs (stmt) == op1)
1242 : {
1243 12982013 : if (!bitmap_set_bit (m_lhs_equiv_set_p, SSA_NAME_VERSION (op1)))
1244 : return false;
1245 : }
1246 30668964 : bool ret = record (gimple_bb (stmt), k, op1, op2);
1247 :
1248 30668964 : if (ret && dump_file && (dump_flags & TDF_DETAILS))
1249 : {
1250 37471 : value_relation vr (k, op1, op2);
1251 37471 : fprintf (dump_file, " Registering value_relation ");
1252 37471 : vr.dump (dump_file);
1253 37471 : fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
1254 37471 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1255 : }
1256 : return ret;
1257 : }
1258 :
1259 : // Register relation K between ssa_name OP1 and OP2 on edge E.
1260 : // Return false if no new relation is added.
1261 :
1262 : bool
1263 6669744 : relation_oracle::record (edge e, relation_kind k, tree op1, tree op2)
1264 : {
1265 6669744 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1266 6669744 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1267 :
1268 : // Do not register lack of relation, or blocks which have more than
1269 : // edge E for a predecessor.
1270 6669744 : if (k == VREL_VARYING || !single_pred_p (e->dest))
1271 : return false;
1272 :
1273 6669744 : bool ret = record (e->dest, k, op1, op2);
1274 :
1275 6669744 : if (ret && dump_file && (dump_flags & TDF_DETAILS))
1276 : {
1277 120 : value_relation vr (k, op1, op2);
1278 120 : fprintf (dump_file, " Registering value_relation ");
1279 120 : vr.dump (dump_file);
1280 120 : fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
1281 : }
1282 : return ret;
1283 : }
1284 :
1285 : // Register relation K between OP! and OP2 in block BB.
1286 : // This creates the record and searches for existing records in the dominator
1287 : // tree to merge with. Return false if no new relation is added.
1288 :
1289 : bool
1290 36274141 : dom_oracle::record (basic_block bb, relation_kind k, tree op1, tree op2)
1291 : {
1292 : // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1293 : // and no other relation makes sense.
1294 36274141 : if (op1 == op2)
1295 : return false;
1296 :
1297 : // Equivalencies are handled by the equivalence oracle.
1298 36263110 : if (relation_equiv_p (k))
1299 14349449 : return equiv_oracle::record (bb, k, op1, op2);
1300 : else
1301 : {
1302 : // if neither op1 nor op2 are in a relation before this is registered,
1303 : // there will be no transitive.
1304 21913661 : bool check = bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op1))
1305 38329344 : || bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op2));
1306 21913661 : relation_chain *ptr = search_and_merge_relation (bb, k, op1, op2);
1307 21913661 : if (ptr && check
1308 21913661 : && (m_relations[bb->index].m_num_relations
1309 6416407 : < param_relation_block_limit))
1310 6416301 : register_transitives (bb, *ptr);
1311 : return ptr != NULL;
1312 : }
1313 : }
1314 :
1315 : void
1316 43035966 : dom_oracle::record_relation_block (unsigned v, unsigned bbi)
1317 : {
1318 43035966 : if (v>= m_block_list.length ())
1319 524 : m_block_list.safe_grow_cleared (num_ssa_names + 1);
1320 :
1321 43035966 : if (!m_block_list[v])
1322 30728246 : m_block_list[v] = BITMAP_ALLOC (&m_bitmaps);
1323 :
1324 43035966 : bitmap_set_bit (m_block_list[v], bbi);
1325 43035966 : }
1326 :
1327 : // Register relation K between OP1 and OP2 in block BB by creating a new
1328 : // record. It is an error for there to be an existing record.
1329 : // Return the record, or NULL if no record was created.
1330 :
1331 : relation_chain *
1332 21574031 : dom_oracle::create_relation_in_bb (basic_block bb, relation_kind k, tree op1,
1333 : tree op2)
1334 : {
1335 21574031 : int bbi = bb->index;
1336 :
1337 43148062 : if (bbi >= (int)m_relations.length())
1338 129 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1339 :
1340 21574031 : if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
1341 : return NULL;
1342 21517983 : m_relations[bbi].m_num_relations++;
1343 : // Check for an existing relation further up the DOM chain.
1344 : // By including dominating relations, The first one found in any search
1345 : // will be the aggregate of all the previous ones.
1346 :
1347 21517983 : relation_chain *ptr;
1348 :
1349 : // Summary bitmap indicating what ssa_names have relations in this BB.
1350 21517983 : bitmap bm = m_relations[bbi].m_names;
1351 21517983 : if (!bm)
1352 14514873 : bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
1353 21517983 : unsigned v1 = SSA_NAME_VERSION (op1);
1354 21517983 : unsigned v2 = SSA_NAME_VERSION (op2);
1355 :
1356 : // Assert there is no existing relation.
1357 21517983 : gcc_checking_assert (find_relation_block (bbi, op1, op2, NULL)
1358 : == VREL_VARYING);
1359 :
1360 21517983 : bitmap_set_bit (bm, v1);
1361 21517983 : bitmap_set_bit (bm, v2);
1362 21517983 : bitmap_set_bit (m_relation_set, v1);
1363 21517983 : bitmap_set_bit (m_relation_set, v2);
1364 21517983 : record_relation_block (v1, bbi);
1365 21517983 : record_relation_block (v2, bbi);
1366 :
1367 21517983 : ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1368 : sizeof (relation_chain));
1369 21517983 : ptr->set_relation (k, op1, op2);
1370 21517983 : ptr->m_next = m_relations[bbi].m_head;
1371 21517983 : m_relations[bbi].m_head = ptr;
1372 21517983 : return ptr;
1373 : }
1374 :
1375 : // Register relation K between OP1 and OP2 in block BB by searching the
1376 : // dominator tree for any existing record to merge with. If there were
1377 : // none, create a new record.
1378 : // Return the record, or NULL if no record was found or created.
1379 :
1380 : relation_chain *
1381 24009163 : dom_oracle::search_and_merge_relation (basic_block bb, relation_kind k,
1382 : tree op1, tree op2)
1383 : {
1384 24009163 : gcc_checking_assert (k != VREL_VARYING && k != VREL_EQ);
1385 :
1386 24009163 : relation_chain *ptr;
1387 24009163 : relation_kind curr = find_relation_block (bb->index, op1, op2, &ptr);
1388 :
1389 : // If there is an existing relation in this block, just intersect with it.
1390 24009163 : if (curr != VREL_VARYING)
1391 : {
1392 : // If there was no change, return no record.
1393 2435132 : value_relation vr (k, op1, op2);
1394 2435132 : if (!ptr->intersect (vr))
1395 : return NULL;
1396 189122 : return ptr;
1397 : }
1398 :
1399 : // Create the relation in this block.
1400 21574031 : ptr = create_relation_in_bb (bb, k, op1, op2);
1401 21574031 : if (ptr)
1402 : {
1403 : // Check for an existing relation further up the DOM chain.
1404 : // By including dominating relations, The first one found in any search
1405 : // will be the aggregate of all the previous ones.
1406 21517983 : curr = find_relation_dom (get_immediate_dominator (CDI_DOMINATORS, bb),
1407 : op1, op2);
1408 21517983 : if (curr != VREL_VARYING)
1409 : {
1410 617918 : curr = relation_intersect (curr, k);
1411 : // Intersect the new relation with the existing one, unless the
1412 : // result is UNDEFINED. Then just leave it.
1413 617918 : if (curr != k && curr != VREL_UNDEFINED)
1414 166702 : ptr->set_relation (curr, op1, op2);
1415 : }
1416 : }
1417 21574031 : return ptr;
1418 : }
1419 :
1420 : // Starting at ROOT_BB search the DOM tree looking for relations which
1421 : // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
1422 : // bitmaps for op1/op2 and any of their equivalences that should also be
1423 : // considered.
1424 :
1425 : void
1426 6416301 : dom_oracle::register_transitives (basic_block root_bb,
1427 : const value_relation &relation)
1428 : {
1429 : // Only register transitives if they are requested.
1430 6416301 : if (!m_do_trans_p)
1431 : return;
1432 6416291 : basic_block bb;
1433 : // Only apply transitives to certain kinds of operations.
1434 6416291 : switch (relation.kind ())
1435 : {
1436 4696019 : case VREL_LE:
1437 4696019 : case VREL_LT:
1438 4696019 : case VREL_GT:
1439 4696019 : case VREL_GE:
1440 4696019 : break;
1441 : default:
1442 : return;
1443 : }
1444 :
1445 4696019 : const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb);
1446 4696019 : const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb);
1447 :
1448 4696019 : const unsigned work_budget = param_transitive_relations_work_bound;
1449 4696019 : unsigned avail_budget = work_budget;
1450 91750744 : for (bb = root_bb; bb;
1451 : /* Advancing to the next immediate dominator eats from the budget,
1452 : if none is left after that there's no point to continue. */
1453 : bb = (--avail_budget > 0
1454 87114995 : ? get_immediate_dominator (CDI_DOMINATORS, bb) : nullptr))
1455 : {
1456 87191965 : int bbi = bb->index;
1457 174383930 : if (bbi >= (int)m_relations.length())
1458 4637 : continue;
1459 87187328 : const_bitmap bm = m_relations[bbi].m_names;
1460 87187328 : if (!bm)
1461 62524900 : continue;
1462 24662428 : if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
1463 16189272 : continue;
1464 : // At least one of the 2 ops has a relation in this block.
1465 8473156 : relation_chain *ptr;
1466 37169961 : for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
1467 : {
1468 : // In the presence of an equivalence, 2 operands may do not
1469 : // naturally match. ie with equivalence a_2 == b_3
1470 : // given c_1 < a_2 && b_3 < d_4
1471 : // convert the second relation (b_3 < d_4) to match any
1472 : // equivalences to found in the first relation.
1473 : // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1474 : // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1475 :
1476 28773775 : tree r1, r2;
1477 28773775 : tree p1 = ptr->op1 ();
1478 28773775 : tree p2 = ptr->op2 ();
1479 : // Find which equivalence is in the first operand.
1480 28773775 : if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
1481 : r1 = p1;
1482 22058734 : else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
1483 : r1 = p2;
1484 : else
1485 21370350 : r1 = NULL_TREE;
1486 :
1487 : // Find which equivalence is in the second operand.
1488 28773775 : if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
1489 : r2 = p1;
1490 26595757 : else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
1491 : r2 = p2;
1492 : else
1493 17354910 : r2 = NULL_TREE;
1494 :
1495 : // Ignore if both NULL (not relevant relation) or the same,
1496 28773775 : if (r1 == r2)
1497 : ;
1498 :
1499 : else
1500 : {
1501 : // Any operand not an equivalence, just take the real operand.
1502 13901279 : if (!r1)
1503 6497904 : r1 = relation.op1 ();
1504 13901279 : if (!r2)
1505 2482464 : r2 = relation.op2 ();
1506 :
1507 13901279 : value_relation nr (relation.kind (), r1, r2);
1508 13901279 : if (nr.apply_transitive (*ptr))
1509 : {
1510 : // If the new relation is already present we know any
1511 : // further processing is already reflected above it.
1512 : // When we ran into the limit of relations on root_bb
1513 : // we can give up as well.
1514 2095502 : if (!search_and_merge_relation (root_bb, nr.kind (),
1515 : nr.op1 (), nr.op2 ()))
1516 70079 : return;
1517 2025423 : if (dump_file && (dump_flags & TDF_DETAILS))
1518 : {
1519 1309 : fprintf (dump_file,
1520 : " Registering transitive relation ");
1521 1309 : nr.dump (dump_file);
1522 1309 : fputc ('\n', dump_file);
1523 : }
1524 : }
1525 : }
1526 : /* Processed one relation, abort if we've eaten up our budget. */
1527 28703696 : if (--avail_budget == 0)
1528 : return;
1529 : }
1530 : }
1531 : }
1532 :
1533 : // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1534 : // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1535 :
1536 : relation_kind
1537 406617604 : dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
1538 : const_bitmap b2) const
1539 : {
1540 406617604 : if (bb >= m_relations.length())
1541 : return VREL_VARYING;
1542 :
1543 406615993 : return m_relations[bb].find_relation (b1, b2);
1544 : }
1545 :
1546 : // Search the DOM tree for a relation between an element of equivalency set B1
1547 : // and B2, starting with block BB.
1548 :
1549 : relation_kind
1550 26034516 : dom_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
1551 : {
1552 26034516 : relation_kind r;
1553 26034516 : if (bitmap_equal_p (b1, b2))
1554 : return VREL_EQ;
1555 :
1556 : // If either name does not occur in a relation anywhere, there isn't one.
1557 26034516 : if (!bitmap_intersect_p (m_relation_set, b1)
1558 26034516 : || !bitmap_intersect_p (m_relation_set, b2))
1559 : return VREL_VARYING;
1560 :
1561 : // Search each block in the DOM tree checking.
1562 421332764 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1563 : {
1564 406617604 : r = find_relation_block (bb->index, b1, b2);
1565 406617604 : if (r != VREL_VARYING)
1566 : return r;
1567 : }
1568 : return VREL_VARYING;
1569 :
1570 : }
1571 :
1572 : // Find a relation in block BB between ssa version V1 and V2. If a relation
1573 : // is found, return a pointer to the chain object in OBJ.
1574 :
1575 : relation_kind
1576 1143239621 : dom_oracle::find_relation_block (int bb, tree ssa1, tree ssa2,
1577 : relation_chain **obj) const
1578 : {
1579 2286479242 : if (bb >= (int)m_relations.length())
1580 : return VREL_VARYING;
1581 :
1582 1143222277 : const_bitmap bm = m_relations[bb].m_names;
1583 1143222277 : if (!bm)
1584 : return VREL_VARYING;
1585 :
1586 514143023 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1587 514143023 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1588 :
1589 : // If both b1 and b2 aren't referenced in this block, cant be a relation
1590 514143023 : if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1591 : return VREL_VARYING;
1592 :
1593 12545117 : relation_chain *ptr;
1594 69583713 : for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1595 : {
1596 66617251 : tree op1 = ptr->op1 ();
1597 66617251 : tree op2 = ptr->op2 ();
1598 66617251 : if (ssa1 == op1 && ssa2 == op2)
1599 : {
1600 9278356 : if (obj)
1601 2434813 : *obj = ptr;
1602 9278356 : return ptr->kind ();
1603 : }
1604 57338895 : if (ssa1 == op2 && ssa2 == op1)
1605 : {
1606 300299 : if (obj)
1607 319 : *obj = ptr;
1608 300299 : return relation_swap (ptr->kind ());
1609 : }
1610 : }
1611 :
1612 : return VREL_VARYING;
1613 : }
1614 :
1615 : // See if a relation can be found between SSA1 and SSA2 in basic block BB based
1616 : // on values as they exist in basic block ORIG. This will only occur
1617 : // if SSA1 and SSA2 occur in the same statement together.
1618 :
1619 : relation_kind
1620 737863568 : dom_oracle::recomputed_relation (basic_block orig_bb, edge e, tree ssa1,
1621 : tree ssa2) const
1622 : {
1623 737863568 : if (ssa1 == ssa2)
1624 : return VREL_EQ;
1625 1475727136 : gori_map *gori_ssa = get_range_query (cfun)->gori_ssa ();
1626 737863568 : if (!gori_ssa)
1627 : return VREL_VARYING;
1628 :
1629 : // If SSA1 and SSA2 are not BOTH exported from the block, theres no relation.
1630 730992354 : basic_block bb = e->src;
1631 730992354 : if (!gori_ssa->is_export_p (ssa1, bb) || !gori_ssa->is_export_p (ssa2, bb))
1632 : return VREL_VARYING;
1633 :
1634 : // Verify the edge is a range generating edge.
1635 776554 : gimple_outgoing_range &gori = get_range_query (cfun)->gori ();
1636 388277 : int_range_max edge_range;
1637 388277 : gimple *stmt = gori.edge_range_p (edge_range, e);
1638 388277 : if (!stmt)
1639 : return VREL_VARYING;
1640 :
1641 : // Scan back thru the dependency chain recalculating values as if they are
1642 : // in ORIG_BB, and see if we can find a statement with both op1 and op2
1643 : // which generates a relation.
1644 :
1645 388277 : value_range lhs_range (edge_range);
1646 :
1647 388277 : while (stmt)
1648 : {
1649 614325 : bool ret;
1650 614325 : gimple_range_op_handler handler (stmt);
1651 614325 : if (!handler)
1652 388277 : return VREL_VARYING;
1653 :
1654 614281 : tree op1 = handler.operand1 ();
1655 614281 : tree op2 = handler.operand2 ();
1656 614281 : value_range op1_range (TREE_TYPE (op1));
1657 614281 : value_range op2_range;
1658 :
1659 : // Check if this is the statment we are looking for!
1660 614281 : bool match = (op1 == ssa1 && op2 == ssa2);
1661 614281 : bool match_rev = (op2 == ssa1 && op1 == ssa2);
1662 614281 : if (match || match_rev)
1663 : {
1664 103851 : gcc_checking_assert (op2);
1665 103851 : op2_range.set_range_class (TREE_TYPE (op2));
1666 : // Pick up the ranges at ORIG_BB, and see if a relation is generated.
1667 207702 : get_range_query (cfun)->range_on_entry (op1_range, orig_bb, op1);
1668 207702 : get_range_query (cfun)->range_on_entry (op2_range, orig_bb, op2);
1669 103851 : relation_kind relation = handler.op1_op2_relation (lhs_range,
1670 103851 : op1_range,
1671 103851 : op2_range);
1672 : // If the operands are reversed, swap the relation.
1673 103851 : if (match_rev)
1674 25543 : relation = relation_swap (relation);
1675 : return relation;
1676 : }
1677 :
1678 : // Now determine if one of the operands has both SSA1 and SSA2 in
1679 : // the dependency chain. Thats the path we want to follow.
1680 510430 : bool op1_dep = gimple_range_ssa_p (op1)
1681 507228 : && gori_ssa->in_chain_p (ssa1, op1)
1682 800442 : && gori_ssa->in_chain_p (ssa2, op1);
1683 510430 : bool op2_dep = gimple_range_ssa_p (op2)
1684 321496 : && gori_ssa->in_chain_p (ssa1, op2)
1685 634829 : && gori_ssa->in_chain_p (ssa2, op2);
1686 : // If there are no dependencies with both names, or both sides have
1687 : // both names, simply bail.
1688 510430 : if (op1_dep == op2_dep)
1689 : return VREL_VARYING;
1690 :
1691 285016 : if (op1_dep)
1692 : {
1693 : // If operand 1 is the chain we are interested in, calcualte its
1694 : // range based on LHS_RANGE.
1695 215657 : if (!op2)
1696 22262 : ret = handler.calc_op1 (op1_range, lhs_range);
1697 : else
1698 : {
1699 : // Pick up the range of op2 as it occurs in the original block.
1700 : // and calculate a range for op1.
1701 193395 : op2_range.set_range_class (TREE_TYPE (op2));
1702 386790 : get_range_query (cfun)->range_on_entry (op2_range, orig_bb, op2);
1703 193395 : ret = handler.calc_op1 (op1_range, lhs_range, op2_range);
1704 : }
1705 : // If we failed to calculate a range for op1, bail.
1706 215657 : if (!ret)
1707 : return VREL_VARYING;
1708 :
1709 : // op1_range will now become the LHS_RANGE for the def statement.
1710 210872 : lhs_range = op1_range;
1711 210872 : stmt = SSA_NAME_DEF_STMT (op1);
1712 : }
1713 69359 : else if (op2_dep)
1714 : {
1715 : // Pick up the range of op1 as it occurs in the original block.
1716 : // and calcalute a range for op2.
1717 69359 : op2_range.set_range_class (TREE_TYPE (op2));
1718 138718 : get_range_query (cfun)->range_on_entry (op1_range, orig_bb, op1);
1719 69359 : ret = handler.calc_op2 (op2_range, lhs_range, op1_range);
1720 : // If we failed to calculate a range for op1, bail.
1721 69359 : if (!ret)
1722 : return VREL_VARYING;
1723 :
1724 : // op2_range will now become the LHS_RANGE for the def statement.
1725 68803 : lhs_range = op2_range;
1726 68803 : stmt = SSA_NAME_DEF_STMT (op2);
1727 : }
1728 : else
1729 0 : gcc_unreachable ();
1730 :
1731 : // Bail if this ssa-name is defined outside this block.
1732 279675 : if (!stmt || gimple_bb (stmt) != e->src)
1733 : return VREL_VARYING;
1734 614281 : }
1735 : return VREL_VARYING;
1736 388277 : }
1737 :
1738 : // Find a relation between SSA version V1 and V2 in the dominator tree
1739 : // starting with block BB
1740 :
1741 : relation_kind
1742 42692280 : dom_oracle::find_relation_dom (basic_block start_bb, tree ssa1, tree ssa2) const
1743 : {
1744 42692280 : relation_kind r;
1745 42692280 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1746 42692280 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1747 : // IF either name does not occur in a relation anywhere, there isn't one.
1748 42692280 : if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1749 : return VREL_VARYING;
1750 : edge outgoing_edge = NULL;
1751 1090553185 : for (basic_block bb = start_bb;
1752 1131590091 : bb;
1753 1090553185 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1754 : {
1755 1097712475 : r = find_relation_block (bb->index, ssa1, ssa2);
1756 : // Now check if recomputed values on the outgoing edge might create
1757 : // a relation.
1758 1097712475 : if (r == VREL_VARYING && outgoing_edge)
1759 : {
1760 737863568 : gcc_checking_assert (outgoing_edge->src == bb);
1761 737863568 : r = recomputed_relation (start_bb, outgoing_edge, ssa1, ssa2);
1762 : }
1763 1097712475 : if (r != VREL_VARYING)
1764 : return r;
1765 :
1766 : // If the dominator is not the only predecessor to this block, there is
1767 : // unlikely to be a viable relation available.
1768 1090553185 : outgoing_edge = single_pred_p (bb) ? single_pred_edge (bb) : NULL;
1769 : }
1770 : return VREL_VARYING;
1771 : }
1772 :
1773 : // Query if there is a relation between SSA1 and SS2 in block BB or a
1774 : // dominator of BB
1775 :
1776 : relation_kind
1777 103330233 : dom_oracle::query (basic_block bb, tree ssa1, tree ssa2)
1778 : {
1779 103330233 : relation_kind kind;
1780 103330233 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1781 103330233 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1782 103330233 : if (v1 == v2)
1783 : return VREL_EQ;
1784 :
1785 : // If v1 or v2 do not have any relations or equivalences, a partial
1786 : // equivalence is the only possibility.
1787 174810787 : if ((!bitmap_bit_p (m_relation_set, v1) && !has_equiv_p (v1))
1788 106383555 : || (!bitmap_bit_p (m_relation_set, v2) && !has_equiv_p (v2)))
1789 81806066 : return partial_equiv (ssa1, ssa2);
1790 :
1791 : // Check for equivalence first. They must be in each equivalency set.
1792 21421933 : const_bitmap equiv1 = equiv_set (ssa1, bb);
1793 21421933 : const_bitmap equiv2 = equiv_set (ssa2, bb);
1794 21421933 : if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
1795 : return VREL_EQ;
1796 :
1797 21304513 : kind = partial_equiv (ssa1, ssa2);
1798 21304513 : if (kind != VREL_VARYING)
1799 : return kind;
1800 :
1801 : // Initially look for a direct relationship and just return that.
1802 21174297 : kind = find_relation_dom (bb, ssa1, ssa2);
1803 21174297 : if (kind != VREL_VARYING)
1804 : return kind;
1805 :
1806 : // Query using the equivalence sets.
1807 14632925 : kind = query (bb, equiv1, equiv2);
1808 14632925 : return kind;
1809 : }
1810 :
1811 : // Dump all the relations in block BB to file F.
1812 :
1813 : void
1814 257 : dom_oracle::dump (FILE *f, basic_block bb) const
1815 : {
1816 257 : equiv_oracle::dump (f,bb);
1817 :
1818 514 : if (bb->index >= (int)m_relations.length ())
1819 220 : return;
1820 257 : if (!m_relations[bb->index].m_names)
1821 : return;
1822 :
1823 37 : value_relation vr;
1824 84 : FOR_EACH_RELATION_BB (this, bb, vr)
1825 : {
1826 47 : fprintf (f, "Relational : ");
1827 47 : vr.dump (f);
1828 47 : fprintf (f, "\n");
1829 : }
1830 : }
1831 :
1832 : // Dump all the relations known to file F.
1833 :
1834 : void
1835 0 : dom_oracle::dump (FILE *f) const
1836 : {
1837 0 : fprintf (f, "Relation dump\n");
1838 0 : for (unsigned i = 0; i < m_relations.length (); i++)
1839 0 : if (BASIC_BLOCK_FOR_FN (cfun, i))
1840 : {
1841 0 : fprintf (f, "BB%d\n", i);
1842 0 : dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
1843 : }
1844 0 : }
1845 :
1846 : void
1847 0 : relation_oracle::debug () const
1848 : {
1849 0 : dump (stderr);
1850 0 : }
1851 :
1852 31760787 : path_oracle::path_oracle (relation_oracle *oracle)
1853 : {
1854 31760787 : set_root_oracle (oracle);
1855 31760787 : bitmap_obstack_initialize (&m_bitmaps);
1856 31760787 : obstack_init (&m_chain_obstack);
1857 :
1858 : // Initialize header records.
1859 31760787 : m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
1860 31760787 : m_equiv.m_bb = NULL;
1861 31760787 : m_equiv.m_next = NULL;
1862 31760787 : m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
1863 31760787 : m_relations.m_head = NULL;
1864 31760787 : m_killed_defs = BITMAP_ALLOC (&m_bitmaps);
1865 31760787 : }
1866 :
1867 63521574 : path_oracle::~path_oracle ()
1868 : {
1869 31760787 : obstack_free (&m_chain_obstack, NULL);
1870 31760787 : bitmap_obstack_release (&m_bitmaps);
1871 63521574 : }
1872 :
1873 : // Clear any range info and relations associated with NAME.
1874 :
1875 : void
1876 0 : path_oracle::clear (tree name)
1877 : {
1878 0 : if (m_root)
1879 0 : m_root->clear (name);
1880 :
1881 0 : m_relations.clear (name);
1882 :
1883 0 : unsigned v = SSA_NAME_VERSION (name);
1884 0 : equiv_chain *ptr = m_equiv.find (v);
1885 0 : if (ptr)
1886 0 : bitmap_clear_bit (ptr->m_names, v);
1887 0 : }
1888 :
1889 : // Return the equiv set for SSA, and if there isn't one, check for equivs
1890 : // starting in block BB.
1891 :
1892 : const_bitmap
1893 148220193 : path_oracle::equiv_set (tree ssa, basic_block bb)
1894 : {
1895 : // Check the list first.
1896 148220193 : equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
1897 148220193 : if (ptr)
1898 82824609 : return ptr->m_names;
1899 :
1900 : // Otherwise defer to the root oracle.
1901 65395584 : if (m_root)
1902 58959223 : return m_root->equiv_set (ssa, bb);
1903 :
1904 : // Allocate a throw away bitmap if there isn't a root oracle.
1905 6436361 : bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
1906 6436361 : bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
1907 6436361 : return tmp;
1908 : }
1909 :
1910 : // Register an equivalence between SSA1 and SSA2 resolving unknowns from
1911 : // block BB. Return false if no new equivalence was added.
1912 :
1913 : bool
1914 8881971 : path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
1915 : {
1916 8881971 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
1917 8881971 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
1918 :
1919 : // Check if they are the same set, if so, we're done.
1920 8881971 : if (bitmap_equal_p (equiv_1, equiv_2))
1921 : return false;
1922 :
1923 : // Don't mess around, simply create a new record and insert it first.
1924 8867166 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
1925 8867166 : valid_equivs (b, equiv_1, bb);
1926 8867166 : valid_equivs (b, equiv_2, bb);
1927 :
1928 8867166 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1929 : sizeof (equiv_chain));
1930 8867166 : ptr->m_names = b;
1931 8867166 : ptr->m_bb = NULL;
1932 8867166 : ptr->m_next = m_equiv.m_next;
1933 8867166 : m_equiv.m_next = ptr;
1934 8867166 : bitmap_ior_into (m_equiv.m_names, b);
1935 8867166 : return true;
1936 : }
1937 :
1938 : // Register killing definition of an SSA_NAME.
1939 :
1940 : void
1941 61790455 : path_oracle::killing_def (tree ssa)
1942 : {
1943 61790455 : if (dump_file && (dump_flags & TDF_DETAILS))
1944 : {
1945 790 : fprintf (dump_file, " Registering killing_def (path_oracle) ");
1946 790 : print_generic_expr (dump_file, ssa, TDF_SLIM);
1947 790 : fprintf (dump_file, "\n");
1948 : }
1949 :
1950 61790455 : unsigned v = SSA_NAME_VERSION (ssa);
1951 :
1952 61790455 : bitmap_set_bit (m_killed_defs, v);
1953 61790455 : bitmap_set_bit (m_equiv.m_names, v);
1954 :
1955 : // Now add an equivalency with itself so we don't look to the root oracle.
1956 61790455 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
1957 61790455 : bitmap_set_bit (b, v);
1958 61790455 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1959 : sizeof (equiv_chain));
1960 61790455 : ptr->m_names = b;
1961 61790455 : ptr->m_bb = NULL;
1962 61790455 : ptr->m_next = m_equiv.m_next;
1963 61790455 : m_equiv.m_next = ptr;
1964 :
1965 : // Walk the relation list and remove SSA from any relations.
1966 61790455 : if (!bitmap_bit_p (m_relations.m_names, v))
1967 : return;
1968 :
1969 116289 : bitmap_clear_bit (m_relations.m_names, v);
1970 116289 : relation_chain **prev = &(m_relations.m_head);
1971 116289 : relation_chain *next = NULL;
1972 397222 : for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
1973 : {
1974 280933 : gcc_checking_assert (*prev == ptr);
1975 280933 : next = ptr->m_next;
1976 280933 : if (SSA_NAME_VERSION (ptr->op1 ()) == v
1977 280933 : || SSA_NAME_VERSION (ptr->op2 ()) == v)
1978 115291 : *prev = ptr->m_next;
1979 : else
1980 165642 : prev = &(ptr->m_next);
1981 : }
1982 : }
1983 :
1984 : // Register relation K between SSA1 and SSA2, resolving unknowns by
1985 : // querying from BB. Return false if no new relation is registered.
1986 :
1987 : bool
1988 31096289 : path_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
1989 : {
1990 : // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1991 : // and no other relation makes sense.
1992 31096289 : if (ssa1 == ssa2)
1993 : return false;
1994 :
1995 31053963 : relation_kind curr = query (bb, ssa1, ssa2);
1996 31053963 : if (curr != VREL_VARYING)
1997 5111347 : k = relation_intersect (curr, k);
1998 :
1999 31053963 : bool ret;
2000 31053963 : if (k == VREL_EQ)
2001 8881971 : ret = register_equiv (bb, ssa1, ssa2);
2002 : else
2003 : {
2004 22171992 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
2005 22171992 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
2006 22171992 : relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
2007 : sizeof (relation_chain));
2008 22171992 : ptr->set_relation (k, ssa1, ssa2);
2009 22171992 : ptr->m_next = m_relations.m_head;
2010 22171992 : m_relations.m_head = ptr;
2011 22171992 : ret = true;
2012 : }
2013 :
2014 31053963 : if (ret && dump_file && (dump_flags & TDF_DETAILS))
2015 : {
2016 305 : value_relation vr (k, ssa1, ssa2);
2017 305 : fprintf (dump_file, " Registering value_relation (path_oracle) ");
2018 305 : vr.dump (dump_file);
2019 305 : fprintf (dump_file, " (root: bb%d)\n", bb->index);
2020 : }
2021 : return ret;
2022 : }
2023 :
2024 : // Query for a relationship between equiv set B1 and B2, resolving unknowns
2025 : // starting at block BB.
2026 :
2027 : relation_kind
2028 55206228 : path_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
2029 : {
2030 55206228 : if (bitmap_equal_p (b1, b2))
2031 : return VREL_EQ;
2032 :
2033 55206228 : relation_kind k = m_relations.find_relation (b1, b2);
2034 :
2035 : // Do not look at the root oracle for names that have been killed
2036 : // along the path.
2037 55206228 : if (bitmap_intersect_p (m_killed_defs, b1)
2038 55206228 : || bitmap_intersect_p (m_killed_defs, b2))
2039 : return k;
2040 :
2041 : // Query the root oracle for relations with path local equivalencies.
2042 13737969 : if (k == VREL_VARYING && m_root)
2043 11401591 : k = m_root->query (bb, b1, b2);
2044 :
2045 : return k;
2046 : }
2047 :
2048 : // Query for a relationship between SSA1 and SSA2, resolving unknowns
2049 : // starting at block BB.
2050 :
2051 : relation_kind
2052 55896068 : path_oracle::query (basic_block bb, tree ssa1, tree ssa2)
2053 : {
2054 55896068 : unsigned v1 = SSA_NAME_VERSION (ssa1);
2055 55896068 : unsigned v2 = SSA_NAME_VERSION (ssa2);
2056 :
2057 55896068 : if (v1 == v2)
2058 : return VREL_EQ;
2059 :
2060 55801732 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
2061 55801732 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
2062 55801732 : if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
2063 : return VREL_EQ;
2064 :
2065 55206228 : relation_kind rel = query (bb, equiv_1, equiv_2);
2066 :
2067 : // If the path relation query fails, check for relations in the root oracle.
2068 55206228 : if (rel == VREL_VARYING && m_root)
2069 48325221 : rel = m_root->query (bb, ssa1, ssa2);
2070 : return rel;
2071 : }
2072 :
2073 : // Reset any relations registered on this path. ORACLE is the root
2074 : // oracle to use.
2075 :
2076 : void
2077 24734767 : path_oracle::reset_path (relation_oracle *oracle)
2078 : {
2079 24734767 : set_root_oracle (oracle);
2080 24734767 : m_equiv.m_next = NULL;
2081 24734767 : bitmap_clear (m_equiv.m_names);
2082 24734767 : m_relations.m_head = NULL;
2083 24734767 : bitmap_clear (m_relations.m_names);
2084 24734767 : bitmap_clear (m_killed_defs);
2085 24734767 : }
2086 :
2087 : // Dump relation in basic block... Do nothing here.
2088 :
2089 : void
2090 0 : path_oracle::dump (FILE *, basic_block) const
2091 : {
2092 0 : }
2093 :
2094 : // Dump the relations and equivalencies found in the path.
2095 :
2096 : void
2097 0 : path_oracle::dump (FILE *f) const
2098 : {
2099 0 : equiv_chain *ptr = m_equiv.m_next;
2100 0 : relation_chain *ptr2 = m_relations.m_head;
2101 :
2102 0 : if (ptr || ptr2)
2103 0 : fprintf (f, "\npath_oracle:\n");
2104 :
2105 0 : for (; ptr; ptr = ptr->m_next)
2106 0 : ptr->dump (f);
2107 :
2108 0 : for (; ptr2; ptr2 = ptr2->m_next)
2109 : {
2110 0 : fprintf (f, "Relational : ");
2111 0 : ptr2->dump (f);
2112 0 : fprintf (f, "\n");
2113 : }
2114 0 : }
2115 :
2116 : // ------------------------------------------------------------------------
2117 : // EQUIV iterator. Although we have bitmap iterators, don't expose that it
2118 : // is currently a bitmap. Use an export iterator to hide future changes.
2119 :
2120 : // Construct a basic iterator over an equivalence bitmap.
2121 :
2122 53092138 : equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle,
2123 : basic_block bb, tree name,
2124 : bool full, bool partial)
2125 : {
2126 53092138 : m_name = name;
2127 53092138 : m_oracle = oracle;
2128 53092138 : m_pe = partial ? oracle->partial_equiv_set (name) : NULL;
2129 53092138 : m_bm = NULL;
2130 53092138 : if (full)
2131 53092138 : m_bm = oracle->equiv_set (name, bb);
2132 53092138 : if (!m_bm && m_pe)
2133 0 : m_bm = m_pe->members;
2134 53092138 : if (m_bm)
2135 53092137 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
2136 53092138 : }
2137 :
2138 : // Move to the next export bitmap spot.
2139 :
2140 : void
2141 69302608 : equiv_relation_iterator::next ()
2142 : {
2143 69302608 : bmp_iter_next (&m_bi, &m_y);
2144 69302608 : }
2145 :
2146 : // Fetch the name of the next export in the export list. Return NULL if
2147 : // iteration is done.
2148 :
2149 : tree
2150 63212479 : equiv_relation_iterator::get_name (relation_kind *rel)
2151 : {
2152 69302455 : if (!m_bm)
2153 : return NULL_TREE;
2154 :
2155 128484721 : while (bmp_iter_set (&m_bi, &m_y))
2156 : {
2157 : // Do not return self.
2158 69302608 : tree t = ssa_name (m_y);
2159 69302608 : if (t && t != m_name)
2160 : {
2161 10120353 : relation_kind k = VREL_EQ;
2162 10120353 : if (m_pe && m_bm == m_pe->members)
2163 : {
2164 7821382 : const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t);
2165 7821382 : if (equiv_pe && equiv_pe->members == m_pe->members)
2166 7821370 : k = pe_min (m_pe->code, equiv_pe->code);
2167 : else
2168 : k = VREL_VARYING;
2169 : }
2170 7821382 : if (relation_equiv_p (k))
2171 : {
2172 10120341 : if (rel)
2173 10120341 : *rel = k;
2174 : return t;
2175 : }
2176 : }
2177 59182267 : next ();
2178 : }
2179 :
2180 : // Process partial equivs after full equivs if both were requested.
2181 59182113 : if (m_pe && m_bm != m_pe->members)
2182 : {
2183 53092137 : m_bm = m_pe->members;
2184 53092137 : if (m_bm)
2185 : {
2186 : // Recursively call back to process First PE.
2187 6089976 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
2188 6089976 : return get_name (rel);
2189 : }
2190 : }
2191 : return NULL_TREE;
2192 : }
2193 :
2194 : #if CHECKING_P
2195 : #include "selftest.h"
2196 :
2197 : namespace selftest
2198 : {
2199 : void
2200 4 : relation_tests ()
2201 : {
2202 : // rr_*_table tables use unsigned char rather than relation_kind.
2203 4 : ASSERT_LT (VREL_LAST, UCHAR_MAX);
2204 : // Verify commutativity of relation_intersect and relation_union.
2205 36 : for (relation_kind r1 = VREL_VARYING; r1 < VREL_PE8;
2206 32 : r1 = relation_kind (r1 + 1))
2207 288 : for (relation_kind r2 = VREL_VARYING; r2 < VREL_PE8;
2208 256 : r2 = relation_kind (r2 + 1))
2209 : {
2210 256 : ASSERT_EQ (relation_intersect (r1, r2), relation_intersect (r2, r1));
2211 256 : ASSERT_EQ (relation_union (r1, r2), relation_union (r2, r1));
2212 : }
2213 4 : }
2214 :
2215 : } // namespace selftest
2216 :
2217 : #endif // CHECKING_P
|
