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