Branch data Line data Source code
1 : : /* Header file for the value range relational processing.
2 : : Copyright (C) 2020-2024 Free Software Foundation, Inc.
3 : : Contributed by Andrew MacLeod <amacleod@redhat.com>
4 : :
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 : 1054 : print_relation (FILE *f, relation_kind rel)
43 : : {
44 : 1054 : fprintf (f, " %s ", kind_string[rel]);
45 : 1054 : }
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 : 14297418 : relation_swap (relation_kind r)
69 : : {
70 : 14297418 : 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 : 81022646 : relation_intersect (relation_kind r1, relation_kind r2)
106 : : {
107 : 81022646 : 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 : 74291682 : relation_union (relation_kind r1, relation_kind r2)
143 : : {
144 : 74291682 : 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 : 6320312 : relation_transitive (relation_kind r1, relation_kind r2)
182 : : {
183 : 6320312 : 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 : 1499549 : adjust_equivalence_range (vrange &range)
192 : : {
193 : 1499549 : if (range.undefined_p () || !is_a<frange> (range))
194 : 1465323 : return;
195 : :
196 : 34226 : frange fr = as_a<frange> (range);
197 : : // If range includes 0 make sure both signs of zero are included.
198 : 34226 : if (fr.contains_p (dconst0) || fr.contains_p (dconstm0))
199 : : {
200 : 18396 : frange zeros (range.type (), dconstm0, dconst0);
201 : 18396 : range.union_ (zeros);
202 : 18396 : }
203 : 34226 : }
204 : :
205 : : // This vector maps a relation to the equivalent tree code.
206 : :
207 : : static const tree_code relation_to_code [VREL_LAST] = {
208 : : ERROR_MARK, ERROR_MARK, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EQ_EXPR,
209 : : NE_EXPR };
210 : :
211 : : // Given an equivalence set EQUIV, set all the bits in B that are still valid
212 : : // members of EQUIV in basic block BB.
213 : :
214 : : void
215 : 17872215 : relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
216 : : {
217 : 17872215 : unsigned i;
218 : 17872215 : bitmap_iterator bi;
219 : 37411300 : EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
220 : : {
221 : 19539085 : tree ssa = ssa_name (i);
222 : 39078169 : if (ssa && !SSA_NAME_IN_FREE_LIST (ssa))
223 : : {
224 : 19539084 : const_bitmap ssa_equiv = equiv_set (ssa, bb);
225 : 19539084 : if (ssa_equiv == equivs)
226 : 19334801 : bitmap_set_bit (b, i);
227 : : }
228 : : }
229 : 17872215 : }
230 : :
231 : : // Return any known relation between SSA1 and SSA2 before stmt S is executed.
232 : : // If GET_RANGE is true, query the range of both operands first to ensure
233 : : // the definitions have been processed and any relations have be created.
234 : :
235 : : relation_kind
236 : 87788666 : relation_oracle::query (gimple *s, tree ssa1, tree ssa2)
237 : : {
238 : 87788666 : if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
239 : : return VREL_VARYING;
240 : 30221460 : return query (gimple_bb (s), ssa1, ssa2);
241 : : }
242 : :
243 : : // Return any known relation between SSA1 and SSA2 on edge E.
244 : : // If GET_RANGE is true, query the range of both operands first to ensure
245 : : // the definitions have been processed and any relations have be created.
246 : :
247 : : relation_kind
248 : 47083132 : relation_oracle::query (edge e, tree ssa1, tree ssa2)
249 : : {
250 : 47083132 : basic_block bb;
251 : 47083132 : if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
252 : : return VREL_VARYING;
253 : :
254 : : // Use destination block if it has a single predecessor, and this picks
255 : : // up any relation on the edge.
256 : : // Otherwise choose the src edge and the result is the same as on-exit.
257 : 34661738 : if (!single_pred_p (e->dest))
258 : 32961598 : bb = e->src;
259 : : else
260 : : bb = e->dest;
261 : :
262 : 34661738 : return query (bb, ssa1, ssa2);
263 : : }
264 : : // -------------------------------------------------------------------------
265 : :
266 : : // The very first element in the m_equiv chain is actually just a summary
267 : : // element in which the m_names bitmap is used to indicate that an ssa_name
268 : : // has an equivalence set in this block.
269 : : // This allows for much faster traversal of the DOM chain, as a search for
270 : : // SSA_NAME simply requires walking the DOM chain until a block is found
271 : : // which has the bit for SSA_NAME set. Then scan for the equivalency set in
272 : : // that block. No previous lists need be searched.
273 : :
274 : : // If SSA has an equivalence in this list, find and return it.
275 : : // Otherwise return NULL.
276 : :
277 : : equiv_chain *
278 : 145429708 : equiv_chain::find (unsigned ssa)
279 : : {
280 : 145429708 : equiv_chain *ptr = NULL;
281 : : // If there are equiv sets and SSA is in one in this list, find it.
282 : : // Otherwise return NULL.
283 : 145429708 : if (bitmap_bit_p (m_names, ssa))
284 : : {
285 : 142166514 : for (ptr = m_next; ptr; ptr = ptr->m_next)
286 : 142166514 : if (bitmap_bit_p (ptr->m_names, ssa))
287 : : break;
288 : : }
289 : 145429708 : return ptr;
290 : : }
291 : :
292 : : // Dump the names in this equivalence set.
293 : :
294 : : void
295 : 11 : equiv_chain::dump (FILE *f) const
296 : : {
297 : 11 : bitmap_iterator bi;
298 : 11 : unsigned i;
299 : :
300 : 11 : if (!m_names || bitmap_empty_p (m_names))
301 : 1 : return;
302 : 10 : fprintf (f, "Equivalence set : [");
303 : 10 : unsigned c = 0;
304 : 26 : EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
305 : : {
306 : 16 : if (ssa_name (i))
307 : : {
308 : 16 : if (c++)
309 : 6 : fprintf (f, ", ");
310 : 16 : print_generic_expr (f, ssa_name (i), TDF_SLIM);
311 : : }
312 : : }
313 : 10 : fprintf (f, "]\n");
314 : : }
315 : :
316 : : // Instantiate an equivalency oracle.
317 : :
318 : 23651832 : equiv_oracle::equiv_oracle ()
319 : : {
320 : 23651832 : bitmap_obstack_initialize (&m_bitmaps);
321 : 23651832 : m_equiv.create (0);
322 : 23651832 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
323 : 23651832 : m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
324 : 23651832 : bitmap_tree_view (m_equiv_set);
325 : 23651832 : obstack_init (&m_chain_obstack);
326 : 23651832 : m_self_equiv.create (0);
327 : 47303664 : m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
328 : 23651832 : m_partial.create (0);
329 : 47303664 : m_partial.safe_grow_cleared (num_ssa_names + 1);
330 : 23651832 : }
331 : :
332 : : // Destruct an equivalency oracle.
333 : :
334 : 23651832 : equiv_oracle::~equiv_oracle ()
335 : : {
336 : 23651832 : m_partial.release ();
337 : 23651832 : m_self_equiv.release ();
338 : 23651832 : obstack_free (&m_chain_obstack, NULL);
339 : 23651832 : m_equiv.release ();
340 : 23651832 : bitmap_obstack_release (&m_bitmaps);
341 : 23651832 : }
342 : :
343 : : // Add a partial equivalence R between OP1 and OP2.
344 : :
345 : : void
346 : 9158396 : equiv_oracle::add_partial_equiv (relation_kind r, tree op1, tree op2)
347 : : {
348 : 9158396 : int v1 = SSA_NAME_VERSION (op1);
349 : 9158396 : int v2 = SSA_NAME_VERSION (op2);
350 : 9158396 : int prec2 = TYPE_PRECISION (TREE_TYPE (op2));
351 : 9158396 : int bits = pe_to_bits (r);
352 : 9158396 : gcc_checking_assert (bits && prec2 >= bits);
353 : :
354 : 18316792 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
355 : 32 : m_partial.safe_grow_cleared (num_ssa_names + 1);
356 : 18316792 : gcc_checking_assert (v1 < (int)m_partial.length ()
357 : : && v2 < (int)m_partial.length ());
358 : :
359 : 9158396 : pe_slice &pe1 = m_partial[v1];
360 : 9158396 : pe_slice &pe2 = m_partial[v2];
361 : :
362 : 9158396 : if (pe1.members)
363 : : {
364 : : // If the definition pe1 already has an entry, either the stmt is
365 : : // being re-evaluated, or the def was used before being registered.
366 : : // In either case, if PE2 has an entry, we simply do nothing.
367 : 148219 : if (pe2.members)
368 : : return;
369 : : // If there are no uses of op2, do not register.
370 : 113 : if (has_zero_uses (op2))
371 : : return;
372 : : // PE1 is the LHS and already has members, so everything in the set
373 : : // should be a slice of PE2 rather than PE1.
374 : 113 : pe2.code = pe_min (r, pe1.code);
375 : 113 : pe2.ssa_base = op2;
376 : 113 : pe2.members = pe1.members;
377 : 113 : bitmap_iterator bi;
378 : 113 : unsigned x;
379 : 339 : EXECUTE_IF_SET_IN_BITMAP (pe1.members, 0, x, bi)
380 : : {
381 : 226 : m_partial[x].ssa_base = op2;
382 : 226 : m_partial[x].code = pe_min (m_partial[x].code, pe2.code);
383 : : }
384 : 113 : bitmap_set_bit (pe1.members, v2);
385 : 113 : return;
386 : : }
387 : 9010177 : if (pe2.members)
388 : : {
389 : : // If there are no uses of op1, do not register.
390 : 672153 : if (has_zero_uses (op1))
391 : : return;
392 : 664799 : pe1.ssa_base = pe2.ssa_base;
393 : : // If pe2 is a 16 bit value, but only an 8 bit copy, we can't be any
394 : : // more than an 8 bit equivalence here, so choose MIN value.
395 : 664799 : pe1.code = pe_min (r, pe2.code);
396 : 664799 : pe1.members = pe2.members;
397 : 664799 : bitmap_set_bit (pe1.members, v1);
398 : : }
399 : : else
400 : : {
401 : : // If there are no uses of either operand, do not register.
402 : 8338024 : if (has_zero_uses (op1) || has_zero_uses (op2))
403 : : return;
404 : : // Neither name has an entry, simply create op1 as slice of op2.
405 : 8253066 : pe2.code = bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2)));
406 : 8253066 : if (pe2.code == VREL_VARYING)
407 : : return;
408 : 8217458 : pe2.ssa_base = op2;
409 : 8217458 : pe2.members = BITMAP_ALLOC (&m_bitmaps);
410 : 8217458 : bitmap_set_bit (pe2.members, v2);
411 : 8217458 : pe1.ssa_base = op2;
412 : 8217458 : pe1.code = r;
413 : 8217458 : pe1.members = pe2.members;
414 : 8217458 : bitmap_set_bit (pe1.members, v1);
415 : : }
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 : 49788924 : equiv_oracle::partial_equiv_set (tree name)
423 : : {
424 : 49788924 : int v = SSA_NAME_VERSION (name);
425 : 99577848 : if (v >= (int)m_partial.length ())
426 : : return NULL;
427 : 49788924 : 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 : 46960007 : equiv_oracle::partial_equiv (tree ssa1, tree ssa2, tree *base) const
436 : : {
437 : 46960007 : int v1 = SSA_NAME_VERSION (ssa1);
438 : 46960007 : int v2 = SSA_NAME_VERSION (ssa2);
439 : :
440 : 93920014 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
441 : : return VREL_VARYING;
442 : :
443 : 46960004 : const pe_slice &pe1 = m_partial[v1];
444 : 46960004 : const pe_slice &pe2 = m_partial[v2];
445 : 46960004 : if (pe1.members && pe2.members == pe1.members)
446 : : {
447 : 807 : if (base)
448 : 0 : *base = pe1.ssa_base;
449 : 807 : 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 : 114259155 : equiv_oracle::equiv_set (tree ssa, basic_block bb)
460 : : {
461 : : // Search the dominator tree for an equivalency.
462 : 114259155 : equiv_chain *equiv = find_equiv_dom (ssa, bb);
463 : 114259155 : if (equiv)
464 : 12083471 : return equiv->m_names;
465 : :
466 : : // Otherwise return a cached equiv set containing just this SSA.
467 : 102175684 : unsigned v = SSA_NAME_VERSION (ssa);
468 : 102175684 : if (v >= m_self_equiv.length ())
469 : 142 : m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
470 : :
471 : 102175684 : if (!m_self_equiv[v])
472 : : {
473 : 29211636 : m_self_equiv[v] = BITMAP_ALLOC (&m_bitmaps);
474 : 29211636 : bitmap_set_bit (m_self_equiv[v], v);
475 : : }
476 : 102175684 : 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 : 85714418 : equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
509 : : {
510 : 171428836 : if (bb >= (int)m_equiv.length () || !m_equiv[bb])
511 : : return NULL;
512 : :
513 : 37042548 : 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 : 128562790 : equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
521 : : {
522 : 128562790 : 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 : 128562790 : 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 : 86633513 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
531 : : {
532 : 85714418 : equiv_chain *ptr = find_equiv_block (v, bb->index);
533 : 85714418 : 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 : 80413 : equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
543 : : {
544 : : // V will have an equivalency now.
545 : 80413 : bitmap_set_bit (m_equiv_set, v);
546 : :
547 : : // If that equiv chain is in this block, simply use it.
548 : 80413 : if (equiv->m_bb == bb)
549 : : {
550 : 22350 : bitmap_set_bit (equiv->m_names, v);
551 : 22350 : bitmap_set_bit (m_equiv[bb->index]->m_names, v);
552 : 22350 : 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 : 58063 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
558 : 58063 : valid_equivs (b, equiv->m_names, bb);
559 : 58063 : bitmap_set_bit (b, v);
560 : 58063 : 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 : 3546566 : 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 : 3546566 : if (equiv_1->m_bb == bb)
574 : : {
575 : 2024740 : 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 : 2024740 : if (equiv_2->m_bb == bb)
579 : 263786 : bitmap_clear (equiv_2->m_names);
580 : : else
581 : : // Ensure the new names are in the summary for BB.
582 : 1760954 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
583 : 2024740 : return NULL;
584 : : }
585 : : // If equiv_2 is in BB, use it for the combined set.
586 : 1521826 : if (equiv_2->m_bb == bb)
587 : : {
588 : 2804 : valid_equivs (equiv_2->m_names, equiv_1->m_names, bb);
589 : : // Ensure the new names are in the summary.
590 : 2804 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
591 : 2804 : return NULL;
592 : : }
593 : :
594 : : // At this point, neither equivalence is from this block.
595 : 1519022 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
596 : 1519022 : valid_equivs (b, equiv_1->m_names, bb);
597 : 1519022 : valid_equivs (b, equiv_2->m_names, bb);
598 : 1519022 : 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 : 6612647 : equiv_oracle::register_initial_def (tree ssa)
607 : : {
608 : 6612647 : if (SSA_NAME_IS_DEFAULT_DEF (ssa))
609 : : return;
610 : 6524992 : basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
611 : :
612 : : // If defining stmt is not in the IL, simply return.
613 : 6524992 : if (!bb)
614 : : return;
615 : 6524991 : gcc_checking_assert (!find_equiv_dom (ssa, bb));
616 : :
617 : 6524991 : unsigned v = SSA_NAME_VERSION (ssa);
618 : 6524991 : bitmap_set_bit (m_equiv_set, v);
619 : 6524991 : bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps);
620 : 6524991 : bitmap_set_bit (equiv_set, v);
621 : 6524991 : 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 : :
631 : : void
632 : 13047718 : equiv_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
633 : : {
634 : : // Process partial equivalencies.
635 : 13047718 : if (relation_partial_equiv_p (k))
636 : : {
637 : 9158396 : add_partial_equiv (k, ssa1, ssa2);
638 : 9158396 : return;
639 : : }
640 : : // Only handle equality relations.
641 : 3889322 : if (k != VREL_EQ)
642 : : return;
643 : :
644 : 3889322 : unsigned v1 = SSA_NAME_VERSION (ssa1);
645 : 3889322 : unsigned v2 = SSA_NAME_VERSION (ssa2);
646 : :
647 : : // If this is the first time an ssa_name has an equivalency registered
648 : : // create a self-equivalency record in the def block.
649 : 3889322 : if (!bitmap_bit_p (m_equiv_set, v1))
650 : 3528513 : register_initial_def (ssa1);
651 : 3889322 : if (!bitmap_bit_p (m_equiv_set, v2))
652 : 3084134 : register_initial_def (ssa2);
653 : :
654 : 3889322 : equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
655 : 3889322 : equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
656 : :
657 : : // Check if they are the same set
658 : 3889322 : if (equiv_1 && equiv_1 == equiv_2)
659 : : return;
660 : :
661 : 3636897 : bitmap equiv_set;
662 : :
663 : : // Case where we have 2 SSA_NAMEs that are not in any set.
664 : 3636897 : if (!equiv_1 && !equiv_2)
665 : : {
666 : 9918 : bitmap_set_bit (m_equiv_set, v1);
667 : 9918 : bitmap_set_bit (m_equiv_set, v2);
668 : :
669 : 9918 : equiv_set = BITMAP_ALLOC (&m_bitmaps);
670 : 9918 : bitmap_set_bit (equiv_set, v1);
671 : 9918 : bitmap_set_bit (equiv_set, v2);
672 : : }
673 : 3626979 : else if (!equiv_1 && equiv_2)
674 : 22732 : equiv_set = register_equiv (bb, v1, equiv_2);
675 : 3604247 : else if (equiv_1 && !equiv_2)
676 : 57681 : equiv_set = register_equiv (bb, v2, equiv_1);
677 : : else
678 : 3546566 : equiv_set = register_equiv (bb, equiv_1, equiv_2);
679 : :
680 : : // A non-null return is a bitmap that is to be added to the current
681 : : // block as a new equivalence.
682 : 3636897 : if (!equiv_set)
683 : : return;
684 : :
685 : 1587003 : add_equiv_to_block (bb, equiv_set);
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 : 8111994 : equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
693 : : {
694 : 8111994 : 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 : 8111994 : limit_check (bb);
699 : 8111994 : if (!m_equiv[bb->index])
700 : : {
701 : 5169574 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
702 : : sizeof (equiv_chain));
703 : 5169574 : ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
704 : 5169574 : bitmap_copy (ptr->m_names, equiv_set);
705 : 5169574 : ptr->m_bb = bb;
706 : 5169574 : ptr->m_next = NULL;
707 : 5169574 : m_equiv[bb->index] = ptr;
708 : : }
709 : :
710 : : // Now create the element for this equiv set and initialize it.
711 : 8111994 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
712 : 8111994 : ptr->m_names = equiv_set;
713 : 8111994 : ptr->m_bb = bb;
714 : 16223988 : gcc_checking_assert (bb->index < (int)m_equiv.length ());
715 : 8111994 : ptr->m_next = m_equiv[bb->index]->m_next;
716 : 8111994 : m_equiv[bb->index]->m_next = ptr;
717 : 8111994 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
718 : 8111994 : }
719 : :
720 : : // Make sure the BB vector is big enough and grow it if needed.
721 : :
722 : : void
723 : 8111994 : equiv_oracle::limit_check (basic_block bb)
724 : : {
725 : 8111994 : int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
726 : 16223988 : if (i >= (int)m_equiv.length ())
727 : 1 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
728 : 8111994 : }
729 : :
730 : : // Dump the equivalence sets in BB to file F.
731 : :
732 : : void
733 : 257 : equiv_oracle::dump (FILE *f, basic_block bb) const
734 : : {
735 : 514 : if (bb->index >= (int)m_equiv.length ())
736 : : return;
737 : : // Process equivalences.
738 : 257 : 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 : 13878 : for (unsigned i = 0; i < num_ssa_names; i++)
746 : : {
747 : 13621 : tree name = ssa_name (i);
748 : 19018 : if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name))
749 : 8224 : continue;
750 : 5397 : if (i >= m_partial.length ())
751 : : break;
752 : 5397 : tree base = m_partial[i].ssa_base;
753 : 5397 : if (base && name != base && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb)
754 : : {
755 : 40 : relation_kind k = partial_equiv (name, base);
756 : 40 : if (k != VREL_VARYING)
757 : : {
758 : 40 : value_relation vr (k, name, base);
759 : 40 : fprintf (f, "Partial equiv ");
760 : 40 : vr.dump (f);
761 : 40 : 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 : : // Negate the current relation.
784 : :
785 : : void
786 : 0 : value_relation::negate ()
787 : : {
788 : 0 : related = relation_negate (related);
789 : 0 : }
790 : :
791 : : // Perform an intersection between 2 relations. *this &&= p.
792 : :
793 : : bool
794 : 3118144 : value_relation::intersect (value_relation &p)
795 : : {
796 : : // Save previous value
797 : 3118144 : relation_kind old = related;
798 : :
799 : 3118144 : if (p.op1 () == op1 () && p.op2 () == op2 ())
800 : 3117322 : related = relation_intersect (kind (), p.kind ());
801 : 822 : else if (p.op2 () == op1 () && p.op1 () == op2 ())
802 : 822 : related = relation_intersect (kind (), relation_swap (p.kind ()));
803 : : else
804 : : return false;
805 : :
806 : 3118144 : return old != related;
807 : : }
808 : :
809 : : // Perform a union between 2 relations. *this ||= p.
810 : :
811 : : bool
812 : 0 : value_relation::union_ (value_relation &p)
813 : : {
814 : : // Save previous value
815 : 0 : relation_kind old = related;
816 : :
817 : 0 : if (p.op1 () == op1 () && p.op2 () == op2 ())
818 : 0 : related = relation_union (kind(), p.kind());
819 : 0 : else if (p.op2 () == op1 () && p.op1 () == op2 ())
820 : 0 : related = relation_union (kind(), relation_swap (p.kind ()));
821 : : else
822 : : return false;
823 : :
824 : 0 : return old != related;
825 : : }
826 : :
827 : : // Identify and apply any transitive relations between REL
828 : : // and THIS. Return true if there was a transformation.
829 : :
830 : : bool
831 : 10221256 : value_relation::apply_transitive (const value_relation &rel)
832 : : {
833 : 10221256 : relation_kind k = VREL_VARYING;
834 : :
835 : : // Identify any common operand, and normalize the relations to
836 : : // the form : A < B B < C produces A < C
837 : 10221256 : if (rel.op1 () == name2)
838 : : {
839 : : // A < B B < C
840 : 1846236 : if (rel.op2 () == name1)
841 : : return false;
842 : 1778553 : k = relation_transitive (kind (), rel.kind ());
843 : 1778553 : if (k != VREL_VARYING)
844 : : {
845 : 659588 : related = k;
846 : 659588 : name2 = rel.op2 ();
847 : 659588 : return true;
848 : : }
849 : : }
850 : 8375020 : else if (rel.op1 () == name1)
851 : : {
852 : : // B > A B < C
853 : 5397299 : if (rel.op2 () == name2)
854 : : return false;
855 : 1564038 : k = relation_transitive (relation_swap (kind ()), rel.kind ());
856 : 1564038 : if (k != VREL_VARYING)
857 : : {
858 : 382755 : related = k;
859 : 382755 : name1 = name2;
860 : 382755 : name2 = rel.op2 ();
861 : 382755 : return true;
862 : : }
863 : : }
864 : 2977721 : else if (rel.op2 () == name2)
865 : : {
866 : : // A < B C > B
867 : 2393122 : if (rel.op1 () == name1)
868 : : return false;
869 : 2393122 : k = relation_transitive (kind (), relation_swap (rel.kind ()));
870 : 2393122 : if (k != VREL_VARYING)
871 : : {
872 : 488847 : related = k;
873 : 488847 : name2 = rel.op1 ();
874 : 488847 : return true;
875 : : }
876 : : }
877 : 584599 : else if (rel.op2 () == name1)
878 : : {
879 : : // B > A C > B
880 : 584599 : if (rel.op1 () == name2)
881 : : return false;
882 : 584599 : k = relation_transitive (relation_swap (kind ()),
883 : : relation_swap (rel.kind ()));
884 : 584599 : if (k != VREL_VARYING)
885 : : {
886 : 220047 : related = k;
887 : 220047 : name1 = name2;
888 : 220047 : name2 = rel.op1 ();
889 : 220047 : return true;
890 : : }
891 : : }
892 : : return false;
893 : : }
894 : :
895 : : // Create a trio from this value relation given LHS, OP1 and OP2.
896 : :
897 : : relation_trio
898 : 38538594 : value_relation::create_trio (tree lhs, tree op1, tree op2)
899 : : {
900 : 38538594 : relation_kind lhs_1;
901 : 38538594 : if (lhs == name1 && op1 == name2)
902 : 87000 : lhs_1 = related;
903 : 38451594 : else if (lhs == name2 && op1 == name1)
904 : 90995 : lhs_1 = relation_swap (related);
905 : : else
906 : : lhs_1 = VREL_VARYING;
907 : :
908 : 38538594 : relation_kind lhs_2;
909 : 38538594 : if (lhs == name1 && op2 == name2)
910 : 51879 : lhs_2 = related;
911 : 38486715 : else if (lhs == name2 && op2 == name1)
912 : 149433 : lhs_2 = relation_swap (related);
913 : : else
914 : : lhs_2 = VREL_VARYING;
915 : :
916 : 38538594 : relation_kind op_op;
917 : 38538594 : if (op1 == name1 && op2 == name2)
918 : 28080295 : op_op = related;
919 : 10458299 : else if (op1 == name2 && op2 == name1)
920 : 0 : op_op = relation_swap (related);
921 : 10458299 : else if (op1 == op2)
922 : : op_op = VREL_EQ;
923 : : else
924 : 10448566 : op_op = VREL_VARYING;
925 : :
926 : 38538594 : return relation_trio (lhs_1, lhs_2, op_op);
927 : : }
928 : :
929 : : // Dump the relation to file F.
930 : :
931 : : void
932 : 1029 : value_relation::dump (FILE *f) const
933 : : {
934 : 1029 : if (!name1 || !name2)
935 : : {
936 : 0 : fprintf (f, "no relation registered");
937 : 0 : return;
938 : : }
939 : 1029 : fputc ('(', f);
940 : 1029 : print_generic_expr (f, op1 (), TDF_SLIM);
941 : 1029 : print_relation (f, kind ());
942 : 1029 : print_generic_expr (f, op2 (), TDF_SLIM);
943 : 1029 : fputc(')', f);
944 : : }
945 : :
946 : : // This container is used to link relations in a chain.
947 : :
948 : : class relation_chain : public value_relation
949 : : {
950 : : public:
951 : : relation_chain *m_next;
952 : : };
953 : :
954 : : // ------------------------------------------------------------------------
955 : :
956 : : // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
957 : : // This will allow equivalencies to be applied to any SSA_NAME in a relation.
958 : :
959 : : relation_kind
960 : 156548561 : relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
961 : : {
962 : 156548561 : if (!m_names)
963 : : return VREL_VARYING;
964 : :
965 : : // If both b1 and b2 aren't referenced in this block, cant be a relation
966 : 107373035 : if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
967 : 103738854 : return VREL_VARYING;
968 : :
969 : : // Search for the first relation that contains BOTH an element from B1
970 : : // and B2, and return that relation.
971 : 11532518 : for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
972 : : {
973 : 10153424 : unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
974 : 10153424 : unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
975 : 10153424 : if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
976 : 2140255 : return ptr->kind ();
977 : 8013169 : if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
978 : 114832 : return relation_swap (ptr->kind ());
979 : : }
980 : :
981 : : return VREL_VARYING;
982 : : }
983 : :
984 : : // Instantiate a relation oracle.
985 : :
986 : 23651832 : dom_oracle::dom_oracle (bool do_trans_p)
987 : : {
988 : 23651832 : m_do_trans_p = do_trans_p;
989 : 23651832 : m_relations.create (0);
990 : 23651832 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
991 : 23651832 : m_relation_set = BITMAP_ALLOC (&m_bitmaps);
992 : 23651832 : m_tmp = BITMAP_ALLOC (&m_bitmaps);
993 : 23651832 : m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
994 : 23651832 : }
995 : :
996 : : // Destruct a relation oracle.
997 : :
998 : 47303664 : dom_oracle::~dom_oracle ()
999 : : {
1000 : 23651832 : m_relations.release ();
1001 : 47303664 : }
1002 : :
1003 : : // Register relation K between ssa_name OP1 and OP2 on STMT.
1004 : :
1005 : : void
1006 : 25134676 : relation_oracle::record (gimple *stmt, relation_kind k, tree op1, tree op2)
1007 : : {
1008 : 25134676 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1009 : 25134676 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1010 : 25134676 : gcc_checking_assert (stmt && gimple_bb (stmt));
1011 : :
1012 : : // Don't register lack of a relation.
1013 : 25134676 : if (k == VREL_VARYING)
1014 : : return;
1015 : :
1016 : 25134676 : if (dump_file && (dump_flags & TDF_DETAILS))
1017 : : {
1018 : 497 : value_relation vr (k, op1, op2);
1019 : 497 : fprintf (dump_file, " Registering value_relation ");
1020 : 497 : vr.dump (dump_file);
1021 : 497 : fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
1022 : 497 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1023 : : }
1024 : :
1025 : : // If an equivalence is being added between a PHI and one of its arguments
1026 : : // make sure that that argument is not defined in the same block.
1027 : : // This can happen along back edges and the equivalence will not be
1028 : : // applicable as it would require a use before def.
1029 : 25134676 : if (k == VREL_EQ && is_a<gphi *> (stmt))
1030 : : {
1031 : 1949881 : tree phi_def = gimple_phi_result (stmt);
1032 : 1949881 : gcc_checking_assert (phi_def == op1 || phi_def == op2);
1033 : 1949881 : tree arg = op2;
1034 : 1949881 : if (phi_def == op2)
1035 : 0 : arg = op1;
1036 : 1949881 : if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
1037 : : {
1038 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1039 : : {
1040 : 0 : fprintf (dump_file, " Not registered due to ");
1041 : 0 : print_generic_expr (dump_file, arg, TDF_SLIM);
1042 : 0 : fprintf (dump_file, " being defined in the same block.\n");
1043 : : }
1044 : 0 : return;
1045 : : }
1046 : : }
1047 : 25134676 : record (gimple_bb (stmt), k, op1, op2);
1048 : : }
1049 : :
1050 : : // Register relation K between ssa_name OP1 and OP2 on edge E.
1051 : :
1052 : : void
1053 : 5832569 : relation_oracle::record (edge e, relation_kind k, tree op1, tree op2)
1054 : : {
1055 : 5832569 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1056 : 5832569 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1057 : :
1058 : : // Do not register lack of relation, or blocks which have more than
1059 : : // edge E for a predecessor.
1060 : 5832569 : if (k == VREL_VARYING || !single_pred_p (e->dest))
1061 : : return;
1062 : :
1063 : 5832569 : if (dump_file && (dump_flags & TDF_DETAILS))
1064 : : {
1065 : 116 : value_relation vr (k, op1, op2);
1066 : 116 : fprintf (dump_file, " Registering value_relation ");
1067 : 116 : vr.dump (dump_file);
1068 : 116 : fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
1069 : : }
1070 : :
1071 : 5832569 : record (e->dest, k, op1, op2);
1072 : : }
1073 : :
1074 : : // Register relation K between OP! and OP2 in block BB.
1075 : : // This creates the record and searches for existing records in the dominator
1076 : : // tree to merge with.
1077 : :
1078 : : void
1079 : 30920588 : dom_oracle::record (basic_block bb, relation_kind k, tree op1, tree op2)
1080 : : {
1081 : : // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1082 : : // and no other relation makes sense.
1083 : 30920588 : if (op1 == op2)
1084 : : return;
1085 : :
1086 : : // Equivalencies are handled by the equivalence oracle.
1087 : 30913764 : if (relation_equiv_p (k))
1088 : 13047718 : equiv_oracle::record (bb, k, op1, op2);
1089 : : else
1090 : : {
1091 : : // if neither op1 nor op2 are in a relation before this is registered,
1092 : : // there will be no transitive.
1093 : 17866046 : bool check = bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op1))
1094 : 30062545 : || bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op2));
1095 : 17866046 : relation_chain *ptr = set_one_relation (bb, k, op1, op2);
1096 : 17866046 : if (ptr && check
1097 : 17866046 : && (m_relations[bb->index].m_num_relations
1098 : 4946652 : < param_relation_block_limit))
1099 : 4946516 : register_transitives (bb, *ptr);
1100 : : }
1101 : : }
1102 : :
1103 : : // Register relation K between OP! and OP2 in block BB.
1104 : : // This creates the record and searches for existing records in the dominator
1105 : : // tree to merge with. Return the record, or NULL if no record was created.
1106 : :
1107 : : relation_chain *
1108 : 19617283 : dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1,
1109 : : tree op2)
1110 : : {
1111 : 19617283 : gcc_checking_assert (k != VREL_VARYING && k != VREL_EQ);
1112 : :
1113 : 19617283 : value_relation vr(k, op1, op2);
1114 : 19617283 : int bbi = bb->index;
1115 : :
1116 : 39234566 : if (bbi >= (int)m_relations.length())
1117 : 25 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1118 : :
1119 : : // Summary bitmap indicating what ssa_names have relations in this BB.
1120 : 19617283 : bitmap bm = m_relations[bbi].m_names;
1121 : 19617283 : if (!bm)
1122 : 11302649 : bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
1123 : 19617283 : unsigned v1 = SSA_NAME_VERSION (op1);
1124 : 19617283 : unsigned v2 = SSA_NAME_VERSION (op2);
1125 : :
1126 : 19617283 : relation_kind curr;
1127 : 19617283 : relation_chain *ptr;
1128 : 19617283 : curr = find_relation_block (bbi, v1, v2, &ptr);
1129 : : // There is an existing relation in this block, just intersect with it.
1130 : 19617283 : if (curr != VREL_VARYING)
1131 : : {
1132 : 3118144 : if (dump_file && (dump_flags & TDF_DETAILS))
1133 : : {
1134 : 17 : fprintf (dump_file, " Intersecting with existing ");
1135 : 17 : ptr->dump (dump_file);
1136 : : }
1137 : : // Check into whether we can simply replace the relation rather than
1138 : : // intersecting it. This may help with some optimistic iterative
1139 : : // updating algorithms.
1140 : 3118144 : bool new_rel = ptr->intersect (vr);
1141 : 3118144 : if (dump_file && (dump_flags & TDF_DETAILS))
1142 : : {
1143 : 17 : fprintf (dump_file, " to produce ");
1144 : 17 : ptr->dump (dump_file);
1145 : 30 : fprintf (dump_file, " %s.\n", new_rel ? "Updated" : "No Change");
1146 : : }
1147 : : // If there was no change, return no record..
1148 : 3118144 : if (!new_rel)
1149 : : return NULL;
1150 : : }
1151 : : else
1152 : : {
1153 : 16499139 : if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
1154 : : {
1155 : 96760 : if (dump_file && (dump_flags & TDF_DETAILS))
1156 : 0 : fprintf (dump_file, " Not registered due to bb being full\n");
1157 : 96760 : return NULL;
1158 : : }
1159 : 16402379 : m_relations[bbi].m_num_relations++;
1160 : : // Check for an existing relation further up the DOM chain.
1161 : : // By including dominating relations, The first one found in any search
1162 : : // will be the aggregate of all the previous ones.
1163 : 16402379 : curr = find_relation_dom (bb, v1, v2);
1164 : 16402379 : if (curr != VREL_VARYING)
1165 : 593522 : k = relation_intersect (curr, k);
1166 : :
1167 : 16402379 : bitmap_set_bit (bm, v1);
1168 : 16402379 : bitmap_set_bit (bm, v2);
1169 : 16402379 : bitmap_set_bit (m_relation_set, v1);
1170 : 16402379 : bitmap_set_bit (m_relation_set, v2);
1171 : :
1172 : 16402379 : ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1173 : : sizeof (relation_chain));
1174 : 16402379 : ptr->set_relation (k, op1, op2);
1175 : 16402379 : ptr->m_next = m_relations[bbi].m_head;
1176 : 16402379 : m_relations[bbi].m_head = ptr;
1177 : : }
1178 : 16584238 : return ptr;
1179 : : }
1180 : :
1181 : : // Starting at ROOT_BB search the DOM tree looking for relations which
1182 : : // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
1183 : : // bitmaps for op1/op2 and any of their equivalences that should also be
1184 : : // considered.
1185 : :
1186 : : void
1187 : 4946516 : dom_oracle::register_transitives (basic_block root_bb,
1188 : : const value_relation &relation)
1189 : : {
1190 : : // Only register transitives if they are requested.
1191 : 4946516 : if (!m_do_trans_p)
1192 : : return;
1193 : 4946506 : basic_block bb;
1194 : : // Only apply transitives to certain kinds of operations.
1195 : 4946506 : switch (relation.kind ())
1196 : : {
1197 : 3690330 : case VREL_LE:
1198 : 3690330 : case VREL_LT:
1199 : 3690330 : case VREL_GT:
1200 : 3690330 : case VREL_GE:
1201 : 3690330 : break;
1202 : : default:
1203 : : return;
1204 : : }
1205 : :
1206 : 3690330 : const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb);
1207 : 3690330 : const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb);
1208 : :
1209 : 3690330 : const unsigned work_budget = param_transitive_relations_work_bound;
1210 : 3690330 : unsigned avail_budget = work_budget;
1211 : 71623728 : for (bb = root_bb; bb;
1212 : : /* Advancing to the next immediate dominator eats from the budget,
1213 : : if none is left after that there's no point to continue. */
1214 : : bb = (--avail_budget > 0
1215 : 67933398 : ? get_immediate_dominator (CDI_DOMINATORS, bb) : nullptr))
1216 : : {
1217 : 68008551 : int bbi = bb->index;
1218 : 136017102 : if (bbi >= (int)m_relations.length())
1219 : 4574 : continue;
1220 : 68003977 : const_bitmap bm = m_relations[bbi].m_names;
1221 : 68003977 : if (!bm)
1222 : 47831056 : continue;
1223 : 20172921 : if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
1224 : 13423747 : continue;
1225 : : // At least one of the 2 ops has a relation in this block.
1226 : 6749174 : relation_chain *ptr;
1227 : 30137172 : for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
1228 : : {
1229 : : // In the presence of an equivalence, 2 operands may do not
1230 : : // naturally match. ie with equivalence a_2 == b_3
1231 : : // given c_1 < a_2 && b_3 < d_4
1232 : : // convert the second relation (b_3 < d_4) to match any
1233 : : // equivalences to found in the first relation.
1234 : : // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1235 : : // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1236 : :
1237 : 23463151 : tree r1, r2;
1238 : 23463151 : tree p1 = ptr->op1 ();
1239 : 23463151 : tree p2 = ptr->op2 ();
1240 : : // Find which equivalence is in the first operand.
1241 : 23463151 : if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
1242 : : r1 = p1;
1243 : 18065291 : else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
1244 : : r1 = p2;
1245 : : else
1246 : 17412841 : r1 = NULL_TREE;
1247 : :
1248 : : // Find which equivalence is in the second operand.
1249 : 23463151 : if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
1250 : : r2 = p1;
1251 : 21616354 : else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
1252 : : r2 = p2;
1253 : : else
1254 : 15389803 : r2 = NULL_TREE;
1255 : :
1256 : : // Ignore if both NULL (not relevant relation) or the same,
1257 : 23463151 : if (r1 == r2)
1258 : : ;
1259 : :
1260 : : else
1261 : : {
1262 : : // Any operand not an equivalence, just take the real operand.
1263 : 10221256 : if (!r1)
1264 : 4171675 : r1 = relation.op1 ();
1265 : 10221256 : if (!r2)
1266 : 2148637 : r2 = relation.op2 ();
1267 : :
1268 : 10221256 : value_relation nr (relation.kind (), r1, r2);
1269 : 10221256 : if (nr.apply_transitive (*ptr))
1270 : : {
1271 : : // If the new relation is already present we know any
1272 : : // further processing is already reflected above it.
1273 : : // When we ran into the limit of relations on root_bb
1274 : : // we can give up as well.
1275 : 1751237 : if (!set_one_relation (root_bb, nr.kind (),
1276 : : nr.op1 (), nr.op2 ()))
1277 : 68471 : return;
1278 : 1682766 : if (dump_file && (dump_flags & TDF_DETAILS))
1279 : : {
1280 : 2 : fprintf (dump_file,
1281 : : " Registering transitive relation ");
1282 : 2 : nr.dump (dump_file);
1283 : 2 : fputc ('\n', dump_file);
1284 : : }
1285 : : }
1286 : : }
1287 : : /* Processed one relation, abort if we've eaten up our budget. */
1288 : 23394680 : if (--avail_budget == 0)
1289 : : return;
1290 : : }
1291 : : }
1292 : : }
1293 : :
1294 : : // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1295 : : // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1296 : :
1297 : : relation_kind
1298 : 115936391 : dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
1299 : : const_bitmap b2) const
1300 : : {
1301 : 115936391 : if (bb >= m_relations.length())
1302 : : return VREL_VARYING;
1303 : :
1304 : 115934898 : return m_relations[bb].find_relation (b1, b2);
1305 : : }
1306 : :
1307 : : // Search the DOM tree for a relation between an element of equivalency set B1
1308 : : // and B2, starting with block BB.
1309 : :
1310 : : relation_kind
1311 : 10839409 : dom_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
1312 : : {
1313 : 10839409 : relation_kind r;
1314 : 10839409 : if (bitmap_equal_p (b1, b2))
1315 : : return VREL_EQ;
1316 : :
1317 : : // If either name does not occur in a relation anywhere, there isn't one.
1318 : 10839409 : if (!bitmap_intersect_p (m_relation_set, b1)
1319 : 10839409 : || !bitmap_intersect_p (m_relation_set, b2))
1320 : 7229747 : return VREL_VARYING;
1321 : :
1322 : : // Search each block in the DOM tree checking.
1323 : 118969778 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1324 : : {
1325 : 115936391 : r = find_relation_block (bb->index, b1, b2);
1326 : 115936391 : if (r != VREL_VARYING)
1327 : : return r;
1328 : : }
1329 : : return VREL_VARYING;
1330 : :
1331 : : }
1332 : :
1333 : : // Find a relation in block BB between ssa version V1 and V2. If a relation
1334 : : // is found, return a pointer to the chain object in OBJ.
1335 : :
1336 : : relation_kind
1337 : 408117870 : dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
1338 : : relation_chain **obj) const
1339 : : {
1340 : 816235740 : if (bb >= (int)m_relations.length())
1341 : : return VREL_VARYING;
1342 : :
1343 : 408112316 : const_bitmap bm = m_relations[bb].m_names;
1344 : 408112316 : if (!bm)
1345 : : return VREL_VARYING;
1346 : :
1347 : : // If both b1 and b2 aren't referenced in this block, cant be a relation
1348 : 335092631 : if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1349 : 324598713 : return VREL_VARYING;
1350 : :
1351 : 10493918 : relation_chain *ptr;
1352 : 50014540 : for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1353 : : {
1354 : 47842687 : unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1355 : 47842687 : unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1356 : 47842687 : if (v1 == op1 && v2 == op2)
1357 : : {
1358 : 8088013 : if (obj)
1359 : 3117322 : *obj = ptr;
1360 : 8088013 : return ptr->kind ();
1361 : : }
1362 : 39754674 : if (v1 == op2 && v2 == op1)
1363 : : {
1364 : 234052 : if (obj)
1365 : 822 : *obj = ptr;
1366 : 234052 : return relation_swap (ptr->kind ());
1367 : : }
1368 : : }
1369 : :
1370 : : return VREL_VARYING;
1371 : : }
1372 : :
1373 : : // Find a relation between SSA version V1 and V2 in the dominator tree
1374 : : // starting with block BB
1375 : :
1376 : : relation_kind
1377 : 23274946 : dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const
1378 : : {
1379 : 23274946 : relation_kind r;
1380 : : // IF either name does not occur in a relation anywhere, there isn't one.
1381 : 23274946 : if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1382 : 13521708 : return VREL_VARYING;
1383 : :
1384 : 393049904 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1385 : : {
1386 : 388500587 : r = find_relation_block (bb->index, v1, v2);
1387 : 388500587 : if (r != VREL_VARYING)
1388 : : return r;
1389 : : }
1390 : : return VREL_VARYING;
1391 : :
1392 : : }
1393 : :
1394 : : // Query if there is a relation between SSA1 and SS2 in block BB or a
1395 : : // dominator of BB
1396 : :
1397 : : relation_kind
1398 : 47282214 : dom_oracle::query (basic_block bb, tree ssa1, tree ssa2)
1399 : : {
1400 : 47282214 : relation_kind kind;
1401 : 47282214 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1402 : 47282214 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1403 : 47282214 : if (v1 == v2)
1404 : : return VREL_EQ;
1405 : :
1406 : : // If v1 or v2 do not have any relations or equivalences, a partial
1407 : : // equivalence is the only possibility.
1408 : 82533283 : if ((!bitmap_bit_p (m_relation_set, v1) && !has_equiv_p (v1))
1409 : 49530571 : || (!bitmap_bit_p (m_relation_set, v2) && !has_equiv_p (v2)))
1410 : 40087327 : return partial_equiv (ssa1, ssa2);
1411 : :
1412 : : // Check for equivalence first. They must be in each equivalency set.
1413 : 7104793 : const_bitmap equiv1 = equiv_set (ssa1, bb);
1414 : 7104793 : const_bitmap equiv2 = equiv_set (ssa2, bb);
1415 : 7104793 : if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
1416 : : return VREL_EQ;
1417 : :
1418 : 6872640 : kind = partial_equiv (ssa1, ssa2);
1419 : 6872640 : if (kind != VREL_VARYING)
1420 : : return kind;
1421 : :
1422 : : // Initially look for a direct relationship and just return that.
1423 : 6872567 : kind = find_relation_dom (bb, v1, v2);
1424 : 6872567 : if (kind != VREL_VARYING)
1425 : : return kind;
1426 : :
1427 : : // Query using the equivalence sets.
1428 : 2262168 : kind = query (bb, equiv1, equiv2);
1429 : 2262168 : return kind;
1430 : : }
1431 : :
1432 : : // Dump all the relations in block BB to file F.
1433 : :
1434 : : void
1435 : 257 : dom_oracle::dump (FILE *f, basic_block bb) const
1436 : : {
1437 : 257 : equiv_oracle::dump (f,bb);
1438 : :
1439 : 514 : if (bb->index >= (int)m_relations.length ())
1440 : : return;
1441 : 257 : if (!m_relations[bb->index].m_names)
1442 : : return;
1443 : :
1444 : 37 : relation_chain *ptr = m_relations[bb->index].m_head;
1445 : 84 : for (; ptr; ptr = ptr->m_next)
1446 : : {
1447 : 47 : fprintf (f, "Relational : ");
1448 : 47 : ptr->dump (f);
1449 : 47 : fprintf (f, "\n");
1450 : : }
1451 : : }
1452 : :
1453 : : // Dump all the relations known to file F.
1454 : :
1455 : : void
1456 : 0 : dom_oracle::dump (FILE *f) const
1457 : : {
1458 : 0 : fprintf (f, "Relation dump\n");
1459 : 0 : for (unsigned i = 0; i < m_relations.length (); i++)
1460 : 0 : if (BASIC_BLOCK_FOR_FN (cfun, i))
1461 : : {
1462 : 0 : fprintf (f, "BB%d\n", i);
1463 : 0 : dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
1464 : : }
1465 : 0 : }
1466 : :
1467 : : void
1468 : 0 : relation_oracle::debug () const
1469 : : {
1470 : 0 : dump (stderr);
1471 : 0 : }
1472 : :
1473 : 24453743 : path_oracle::path_oracle (relation_oracle *oracle)
1474 : : {
1475 : 24453743 : set_root_oracle (oracle);
1476 : 24453743 : bitmap_obstack_initialize (&m_bitmaps);
1477 : 24453743 : obstack_init (&m_chain_obstack);
1478 : :
1479 : : // Initialize header records.
1480 : 24453743 : m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
1481 : 24453743 : m_equiv.m_bb = NULL;
1482 : 24453743 : m_equiv.m_next = NULL;
1483 : 24453743 : m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
1484 : 24453743 : m_relations.m_head = NULL;
1485 : 24453743 : m_killed_defs = BITMAP_ALLOC (&m_bitmaps);
1486 : 24453743 : }
1487 : :
1488 : 48907486 : path_oracle::~path_oracle ()
1489 : : {
1490 : 24453743 : obstack_free (&m_chain_obstack, NULL);
1491 : 24453743 : bitmap_obstack_release (&m_bitmaps);
1492 : 48907486 : }
1493 : :
1494 : : // Return the equiv set for SSA, and if there isn't one, check for equivs
1495 : : // starting in block BB.
1496 : :
1497 : : const_bitmap
1498 : 108387160 : path_oracle::equiv_set (tree ssa, basic_block bb)
1499 : : {
1500 : : // Check the list first.
1501 : 108387160 : equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
1502 : 108387160 : if (ptr)
1503 : 59916786 : return ptr->m_names;
1504 : :
1505 : : // Otherwise defer to the root oracle.
1506 : 48470374 : if (m_root)
1507 : 43287828 : return m_root->equiv_set (ssa, bb);
1508 : :
1509 : : // Allocate a throw away bitmap if there isn't a root oracle.
1510 : 5182546 : bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
1511 : 5182546 : bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
1512 : 5182546 : return tmp;
1513 : : }
1514 : :
1515 : : // Register an equivalence between SSA1 and SSA2 resolving unknowns from
1516 : : // block BB.
1517 : :
1518 : : void
1519 : 6383911 : path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
1520 : : {
1521 : 6383911 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
1522 : 6383911 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
1523 : :
1524 : : // Check if they are the same set, if so, we're done.
1525 : 6383911 : if (bitmap_equal_p (equiv_1, equiv_2))
1526 : : return;
1527 : :
1528 : : // Don't mess around, simply create a new record and insert it first.
1529 : 6374282 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
1530 : 6374282 : valid_equivs (b, equiv_1, bb);
1531 : 6374282 : valid_equivs (b, equiv_2, bb);
1532 : :
1533 : 6374282 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1534 : : sizeof (equiv_chain));
1535 : 6374282 : ptr->m_names = b;
1536 : 6374282 : ptr->m_bb = NULL;
1537 : 6374282 : ptr->m_next = m_equiv.m_next;
1538 : 6374282 : m_equiv.m_next = ptr;
1539 : 6374282 : bitmap_ior_into (m_equiv.m_names, b);
1540 : : }
1541 : :
1542 : : // Register killing definition of an SSA_NAME.
1543 : :
1544 : : void
1545 : 47240262 : path_oracle::killing_def (tree ssa)
1546 : : {
1547 : 47240262 : if (dump_file && (dump_flags & TDF_DETAILS))
1548 : : {
1549 : 811 : fprintf (dump_file, " Registering killing_def (path_oracle) ");
1550 : 811 : print_generic_expr (dump_file, ssa, TDF_SLIM);
1551 : 811 : fprintf (dump_file, "\n");
1552 : : }
1553 : :
1554 : 47240262 : unsigned v = SSA_NAME_VERSION (ssa);
1555 : :
1556 : 47240262 : bitmap_set_bit (m_killed_defs, v);
1557 : 47240262 : bitmap_set_bit (m_equiv.m_names, v);
1558 : :
1559 : : // Now add an equivalency with itself so we don't look to the root oracle.
1560 : 47240262 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
1561 : 47240262 : bitmap_set_bit (b, v);
1562 : 47240262 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1563 : : sizeof (equiv_chain));
1564 : 47240262 : ptr->m_names = b;
1565 : 47240262 : ptr->m_bb = NULL;
1566 : 47240262 : ptr->m_next = m_equiv.m_next;
1567 : 47240262 : m_equiv.m_next = ptr;
1568 : :
1569 : : // Walk the relation list and remove SSA from any relations.
1570 : 47240262 : if (!bitmap_bit_p (m_relations.m_names, v))
1571 : : return;
1572 : :
1573 : 110154 : bitmap_clear_bit (m_relations.m_names, v);
1574 : 110154 : relation_chain **prev = &(m_relations.m_head);
1575 : 110154 : relation_chain *next = NULL;
1576 : 380696 : for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
1577 : : {
1578 : 270542 : gcc_checking_assert (*prev == ptr);
1579 : 270542 : next = ptr->m_next;
1580 : 270542 : if (SSA_NAME_VERSION (ptr->op1 ()) == v
1581 : 270542 : || SSA_NAME_VERSION (ptr->op2 ()) == v)
1582 : 108798 : *prev = ptr->m_next;
1583 : : else
1584 : 161744 : prev = &(ptr->m_next);
1585 : : }
1586 : : }
1587 : :
1588 : : // Register relation K between SSA1 and SSA2, resolving unknowns by
1589 : : // querying from BB.
1590 : :
1591 : : void
1592 : 22192573 : path_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
1593 : : {
1594 : : // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1595 : : // and no other relation makes sense.
1596 : 22192573 : if (ssa1 == ssa2)
1597 : : return;
1598 : :
1599 : 22180735 : if (dump_file && (dump_flags & TDF_DETAILS))
1600 : : {
1601 : 293 : value_relation vr (k, ssa1, ssa2);
1602 : 293 : fprintf (dump_file, " Registering value_relation (path_oracle) ");
1603 : 293 : vr.dump (dump_file);
1604 : 293 : fprintf (dump_file, " (root: bb%d)\n", bb->index);
1605 : : }
1606 : :
1607 : 22180735 : relation_kind curr = query (bb, ssa1, ssa2);
1608 : 22180735 : if (curr != VREL_VARYING)
1609 : 1721602 : k = relation_intersect (curr, k);
1610 : :
1611 : 22180735 : if (k == VREL_EQ)
1612 : : {
1613 : 6383911 : register_equiv (bb, ssa1, ssa2);
1614 : 6383911 : return;
1615 : : }
1616 : :
1617 : 15796824 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
1618 : 15796824 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
1619 : 15796824 : relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1620 : : sizeof (relation_chain));
1621 : 15796824 : ptr->set_relation (k, ssa1, ssa2);
1622 : 15796824 : ptr->m_next = m_relations.m_head;
1623 : 15796824 : m_relations.m_head = ptr;
1624 : : }
1625 : :
1626 : : // Query for a relationship between equiv set B1 and B2, resolving unknowns
1627 : : // starting at block BB.
1628 : :
1629 : : relation_kind
1630 : 40613663 : path_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
1631 : : {
1632 : 40613663 : if (bitmap_equal_p (b1, b2))
1633 : : return VREL_EQ;
1634 : :
1635 : 40613663 : relation_kind k = m_relations.find_relation (b1, b2);
1636 : :
1637 : : // Do not look at the root oracle for names that have been killed
1638 : : // along the path.
1639 : 40613663 : if (bitmap_intersect_p (m_killed_defs, b1)
1640 : 40613663 : || bitmap_intersect_p (m_killed_defs, b2))
1641 : 30099356 : return k;
1642 : :
1643 : 10514307 : if (k == VREL_VARYING && m_root)
1644 : 8577241 : k = m_root->query (bb, b1, b2);
1645 : :
1646 : : return k;
1647 : : }
1648 : :
1649 : : // Query for a relationship between SSA1 and SSA2, resolving unknowns
1650 : : // starting at block BB.
1651 : :
1652 : : relation_kind
1653 : 41054975 : path_oracle::query (basic_block bb, tree ssa1, tree ssa2)
1654 : : {
1655 : 41054975 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1656 : 41054975 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1657 : :
1658 : 41054975 : if (v1 == v2)
1659 : : return VREL_EQ;
1660 : :
1661 : 40992686 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
1662 : 40992686 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
1663 : 40992686 : if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
1664 : : return VREL_EQ;
1665 : :
1666 : 40613663 : return query (bb, equiv_1, equiv_2);
1667 : : }
1668 : :
1669 : : // Reset any relations registered on this path. ORACLE is the root
1670 : : // oracle to use.
1671 : :
1672 : : void
1673 : 19824739 : path_oracle::reset_path (relation_oracle *oracle)
1674 : : {
1675 : 19824739 : set_root_oracle (oracle);
1676 : 19824739 : m_equiv.m_next = NULL;
1677 : 19824739 : bitmap_clear (m_equiv.m_names);
1678 : 19824739 : m_relations.m_head = NULL;
1679 : 19824739 : bitmap_clear (m_relations.m_names);
1680 : 19824739 : bitmap_clear (m_killed_defs);
1681 : 19824739 : }
1682 : :
1683 : : // Dump relation in basic block... Do nothing here.
1684 : :
1685 : : void
1686 : 0 : path_oracle::dump (FILE *, basic_block) const
1687 : : {
1688 : 0 : }
1689 : :
1690 : : // Dump the relations and equivalencies found in the path.
1691 : :
1692 : : void
1693 : 0 : path_oracle::dump (FILE *f) const
1694 : : {
1695 : 0 : equiv_chain *ptr = m_equiv.m_next;
1696 : 0 : relation_chain *ptr2 = m_relations.m_head;
1697 : :
1698 : 0 : if (ptr || ptr2)
1699 : 0 : fprintf (f, "\npath_oracle:\n");
1700 : :
1701 : 0 : for (; ptr; ptr = ptr->m_next)
1702 : 0 : ptr->dump (f);
1703 : :
1704 : 0 : for (; ptr2; ptr2 = ptr2->m_next)
1705 : : {
1706 : 0 : fprintf (f, "Relational : ");
1707 : 0 : ptr2->dump (f);
1708 : 0 : fprintf (f, "\n");
1709 : : }
1710 : 0 : }
1711 : :
1712 : : // ------------------------------------------------------------------------
1713 : : // EQUIV iterator. Although we have bitmap iterators, don't expose that it
1714 : : // is currently a bitmap. Use an export iterator to hide future changes.
1715 : :
1716 : : // Construct a basic iterator over an equivalence bitmap.
1717 : :
1718 : 43475963 : equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle,
1719 : : basic_block bb, tree name,
1720 : 43475963 : bool full, bool partial)
1721 : : {
1722 : 43475963 : m_name = name;
1723 : 43475963 : m_oracle = oracle;
1724 : 43475963 : m_pe = partial ? oracle->partial_equiv_set (name) : NULL;
1725 : 43475963 : m_bm = NULL;
1726 : 43475963 : if (full)
1727 : 43475963 : m_bm = oracle->equiv_set (name, bb);
1728 : 43475963 : if (!m_bm && m_pe)
1729 : 0 : m_bm = m_pe->members;
1730 : 43475963 : if (m_bm)
1731 : 43475963 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
1732 : 43475963 : }
1733 : :
1734 : : // Move to the next export bitmap spot.
1735 : :
1736 : : void
1737 : 56334810 : equiv_relation_iterator::next ()
1738 : : {
1739 : 56334810 : bmp_iter_next (&m_bi, &m_y);
1740 : 56334810 : }
1741 : :
1742 : : // Fetch the name of the next export in the export list. Return NULL if
1743 : : // iteration is done.
1744 : :
1745 : : tree
1746 : 51490167 : equiv_relation_iterator::get_name (relation_kind *rel)
1747 : : {
1748 : 56334755 : if (!m_bm)
1749 : : return NULL_TREE;
1750 : :
1751 : 104655361 : while (bmp_iter_set (&m_bi, &m_y))
1752 : : {
1753 : : // Do not return self.
1754 : 56334810 : tree t = ssa_name (m_y);
1755 : 56334810 : if (t && t != m_name)
1756 : : {
1757 : 8014204 : relation_kind k = VREL_EQ;
1758 : 8014204 : if (m_pe && m_bm == m_pe->members)
1759 : : {
1760 : 6312961 : const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t);
1761 : 6312961 : if (equiv_pe && equiv_pe->members == m_pe->members)
1762 : 6312961 : k = pe_min (m_pe->code, equiv_pe->code);
1763 : : else
1764 : : k = VREL_VARYING;
1765 : : }
1766 : 6312961 : if (relation_equiv_p (k))
1767 : : {
1768 : 8014204 : if (rel)
1769 : 8014204 : *rel = k;
1770 : 8014204 : return t;
1771 : : }
1772 : : }
1773 : 48320606 : next ();
1774 : : }
1775 : :
1776 : : // Process partial equivs after full equivs if both were requested.
1777 : 48320551 : if (m_pe && m_bm != m_pe->members)
1778 : : {
1779 : 43475963 : m_bm = m_pe->members;
1780 : 43475963 : if (m_bm)
1781 : : {
1782 : : // Recursively call back to process First PE.
1783 : 4844588 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
1784 : 4844588 : return get_name (rel);
1785 : : }
1786 : : }
1787 : : return NULL_TREE;
1788 : : }
1789 : :
1790 : : #if CHECKING_P
1791 : : #include "selftest.h"
1792 : :
1793 : : namespace selftest
1794 : : {
1795 : : void
1796 : 4 : relation_tests ()
1797 : : {
1798 : : // rr_*_table tables use unsigned char rather than relation_kind.
1799 : 4 : ASSERT_LT (VREL_LAST, UCHAR_MAX);
1800 : : // Verify commutativity of relation_intersect and relation_union.
1801 : 36 : for (relation_kind r1 = VREL_VARYING; r1 < VREL_PE8;
1802 : 32 : r1 = relation_kind (r1 + 1))
1803 : 288 : for (relation_kind r2 = VREL_VARYING; r2 < VREL_PE8;
1804 : 256 : r2 = relation_kind (r2 + 1))
1805 : : {
1806 : 256 : ASSERT_EQ (relation_intersect (r1, r2), relation_intersect (r2, r1));
1807 : 256 : ASSERT_EQ (relation_union (r1, r2), relation_union (r2, r1));
1808 : : }
1809 : 4 : }
1810 : :
1811 : : } // namespace selftest
1812 : :
1813 : : #endif // CHECKING_P
|
