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 : 1070 : print_relation (FILE *f, relation_kind rel)
43 : : {
44 : 1070 : fprintf (f, " %s ", kind_string[rel]);
45 : 1070 : }
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 : 13687690 : relation_swap (relation_kind r)
69 : : {
70 : 13687690 : 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 : 79113595 : relation_intersect (relation_kind r1, relation_kind r2)
106 : : {
107 : 79113595 : 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 : 72905453 : relation_union (relation_kind r1, relation_kind r2)
143 : : {
144 : 72905453 : 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 : 6264333 : relation_transitive (relation_kind r1, relation_kind r2)
182 : : {
183 : 6264333 : 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 : 1194852 : adjust_equivalence_range (vrange &range)
192 : : {
193 : 1194852 : if (range.undefined_p () || !is_a<frange> (range))
194 : 1162629 : return;
195 : :
196 : 32223 : frange fr = as_a<frange> (range);
197 : : // If range includes 0 make sure both signs of zero are included.
198 : 32223 : if (fr.contains_p (dconst0) || fr.contains_p (dconstm0))
199 : : {
200 : 17950 : frange zeros (range.type (), dconstm0, dconst0);
201 : 17950 : range.union_ (zeros);
202 : : }
203 : : }
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 : : // This routine validates that a relation can be applied to a specific set of
212 : : // ranges. In particular, floating point x == x may not be true if the NaN bit
213 : : // is set in the range. Symbolically the oracle will determine x == x,
214 : : // but specific range instances may override this.
215 : : // To verify, attempt to fold the relation using the supplied ranges.
216 : : // One would expect [1,1] to be returned, anything else means there is something
217 : : // in the range preventing the relation from applying.
218 : : // If there is no mechanism to verify, assume the relation is acceptable.
219 : :
220 : : relation_kind
221 : 0 : relation_oracle::validate_relation (relation_kind rel, vrange &op1, vrange &op2)
222 : : {
223 : : // If there is no mapping to a tree code, leave the relation as is.
224 : 0 : tree_code code = relation_to_code [rel];
225 : 0 : if (code == ERROR_MARK)
226 : : return rel;
227 : :
228 : : // Undefined ranges cannot be checked either.
229 : 0 : if (op1.undefined_p () || op2.undefined_p ())
230 : : return rel;
231 : :
232 : 0 : tree t1 = op1.type ();
233 : 0 : tree t2 = op2.type ();
234 : :
235 : : // If the range types are not compatible, no relation can exist.
236 : 0 : if (!range_compatible_p (t1, t2))
237 : : return VREL_VARYING;
238 : :
239 : : // If there is no handler, leave the relation as is.
240 : 0 : range_op_handler handler (code);
241 : 0 : if (!handler)
242 : : return rel;
243 : :
244 : : // If the relation cannot be folded for any reason, leave as is.
245 : 0 : Value_Range result (boolean_type_node);
246 : 0 : if (!handler.fold_range (result, boolean_type_node, op1, op2,
247 : : relation_trio::op1_op2 (rel)))
248 : : return rel;
249 : :
250 : : // The expression op1 REL op2 using REL should fold to [1,1].
251 : : // Any other result means the relation is not verified to be true.
252 : 0 : if (result.varying_p () || result.zero_p ())
253 : 0 : return VREL_VARYING;
254 : :
255 : : return rel;
256 : 0 : }
257 : :
258 : : // If no range is available, create a varying range for each SSA name and
259 : : // verify.
260 : :
261 : : relation_kind
262 : 0 : relation_oracle::validate_relation (relation_kind rel, tree ssa1, tree ssa2)
263 : : {
264 : 0 : Value_Range op1, op2;
265 : 0 : op1.set_varying (TREE_TYPE (ssa1));
266 : 0 : op2.set_varying (TREE_TYPE (ssa2));
267 : :
268 : 0 : return validate_relation (rel, op1, op2);
269 : 0 : }
270 : :
271 : : // Given an equivalence set EQUIV, set all the bits in B that are still valid
272 : : // members of EQUIV in basic block BB.
273 : :
274 : : void
275 : 17619237 : relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
276 : : {
277 : 17619237 : unsigned i;
278 : 17619237 : bitmap_iterator bi;
279 : 36595824 : EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
280 : : {
281 : 18976587 : tree ssa = ssa_name (i);
282 : 37953173 : if (ssa && !SSA_NAME_IN_FREE_LIST (ssa))
283 : : {
284 : 18976586 : const_bitmap ssa_equiv = equiv_set (ssa, bb);
285 : 18976586 : if (ssa_equiv == equivs)
286 : 18797056 : bitmap_set_bit (b, i);
287 : : }
288 : : }
289 : 17619237 : }
290 : :
291 : : // -------------------------------------------------------------------------
292 : :
293 : : // The very first element in the m_equiv chain is actually just a summary
294 : : // element in which the m_names bitmap is used to indicate that an ssa_name
295 : : // has an equivalence set in this block.
296 : : // This allows for much faster traversal of the DOM chain, as a search for
297 : : // SSA_NAME simply requires walking the DOM chain until a block is found
298 : : // which has the bit for SSA_NAME set. Then scan for the equivalency set in
299 : : // that block. No previous lists need be searched.
300 : :
301 : : // If SSA has an equivalence in this list, find and return it.
302 : : // Otherwise return NULL.
303 : :
304 : : equiv_chain *
305 : 138514732 : equiv_chain::find (unsigned ssa)
306 : : {
307 : 138514732 : equiv_chain *ptr = NULL;
308 : : // If there are equiv sets and SSA is in one in this list, find it.
309 : : // Otherwise return NULL.
310 : 138514732 : if (bitmap_bit_p (m_names, ssa))
311 : : {
312 : 138887288 : for (ptr = m_next; ptr; ptr = ptr->m_next)
313 : 138887288 : if (bitmap_bit_p (ptr->m_names, ssa))
314 : : break;
315 : : }
316 : 138514732 : return ptr;
317 : : }
318 : :
319 : : // Dump the names in this equivalence set.
320 : :
321 : : void
322 : 11 : equiv_chain::dump (FILE *f) const
323 : : {
324 : 11 : bitmap_iterator bi;
325 : 11 : unsigned i;
326 : :
327 : 11 : if (!m_names || bitmap_empty_p (m_names))
328 : 0 : return;
329 : 11 : fprintf (f, "Equivalence set : [");
330 : 11 : unsigned c = 0;
331 : 28 : EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
332 : : {
333 : 17 : if (ssa_name (i))
334 : : {
335 : 17 : if (c++)
336 : 6 : fprintf (f, ", ");
337 : 17 : print_generic_expr (f, ssa_name (i), TDF_SLIM);
338 : : }
339 : : }
340 : 11 : fprintf (f, "]\n");
341 : : }
342 : :
343 : : // Instantiate an equivalency oracle.
344 : :
345 : 23395808 : equiv_oracle::equiv_oracle ()
346 : : {
347 : 23395808 : bitmap_obstack_initialize (&m_bitmaps);
348 : 23395808 : m_equiv.create (0);
349 : 23395808 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
350 : 23395808 : m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
351 : 23395808 : obstack_init (&m_chain_obstack);
352 : 23395808 : m_self_equiv.create (0);
353 : 46791616 : m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
354 : 23395808 : m_partial.create (0);
355 : 46791616 : m_partial.safe_grow_cleared (num_ssa_names + 1);
356 : 23395808 : }
357 : :
358 : : // Destruct an equivalency oracle.
359 : :
360 : 23395808 : equiv_oracle::~equiv_oracle ()
361 : : {
362 : 23395808 : m_partial.release ();
363 : 23395808 : m_self_equiv.release ();
364 : 23395808 : obstack_free (&m_chain_obstack, NULL);
365 : 23395808 : m_equiv.release ();
366 : 23395808 : bitmap_obstack_release (&m_bitmaps);
367 : 23395808 : }
368 : :
369 : : // Add a partial equivalence R between OP1 and OP2.
370 : :
371 : : void
372 : 8345209 : equiv_oracle::add_partial_equiv (relation_kind r, tree op1, tree op2)
373 : : {
374 : 8345209 : int v1 = SSA_NAME_VERSION (op1);
375 : 8345209 : int v2 = SSA_NAME_VERSION (op2);
376 : 8345209 : int prec2 = TYPE_PRECISION (TREE_TYPE (op2));
377 : 8345209 : int bits = pe_to_bits (r);
378 : 8345209 : gcc_checking_assert (bits && prec2 >= bits);
379 : :
380 : 16690418 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
381 : 12 : m_partial.safe_grow_cleared (num_ssa_names + 1);
382 : 16690418 : gcc_checking_assert (v1 < (int)m_partial.length ()
383 : : && v2 < (int)m_partial.length ());
384 : :
385 : 8345209 : pe_slice &pe1 = m_partial[v1];
386 : 8345209 : pe_slice &pe2 = m_partial[v2];
387 : :
388 : 8345209 : if (pe1.members)
389 : : {
390 : : // If the definition pe1 already has an entry, either the stmt is
391 : : // being re-evaluated, or the def was used before being registered.
392 : : // In either case, if PE2 has an entry, we simply do nothing.
393 : 69243 : if (pe2.members)
394 : : return;
395 : : // If there are no uses of op2, do not register.
396 : 65 : if (has_zero_uses (op2))
397 : : return;
398 : : // PE1 is the LHS and already has members, so everything in the set
399 : : // should be a slice of PE2 rather than PE1.
400 : 65 : pe2.code = pe_min (r, pe1.code);
401 : 65 : pe2.ssa_base = op2;
402 : 65 : pe2.members = pe1.members;
403 : 65 : bitmap_iterator bi;
404 : 65 : unsigned x;
405 : 195 : EXECUTE_IF_SET_IN_BITMAP (pe1.members, 0, x, bi)
406 : : {
407 : 130 : m_partial[x].ssa_base = op2;
408 : 130 : m_partial[x].code = pe_min (m_partial[x].code, pe2.code);
409 : : }
410 : 65 : bitmap_set_bit (pe1.members, v2);
411 : 65 : return;
412 : : }
413 : 8275966 : if (pe2.members)
414 : : {
415 : : // If there are no uses of op1, do not register.
416 : 636333 : if (has_zero_uses (op1))
417 : : return;
418 : 629024 : pe1.ssa_base = pe2.ssa_base;
419 : : // If pe2 is a 16 bit value, but only an 8 bit copy, we can't be any
420 : : // more than an 8 bit equivalence here, so choose MIN value.
421 : 629024 : pe1.code = pe_min (r, pe2.code);
422 : 629024 : pe1.members = pe2.members;
423 : 629024 : bitmap_set_bit (pe1.members, v1);
424 : : }
425 : : else
426 : : {
427 : : // If there are no uses of either operand, do not register.
428 : 7639633 : if (has_zero_uses (op1) || has_zero_uses (op2))
429 : : return;
430 : : // Neither name has an entry, simply create op1 as slice of op2.
431 : 7563442 : pe2.code = bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2)));
432 : 7563442 : if (pe2.code == VREL_VARYING)
433 : : return;
434 : 7532787 : pe2.ssa_base = op2;
435 : 7532787 : pe2.members = BITMAP_ALLOC (&m_bitmaps);
436 : 7532787 : bitmap_set_bit (pe2.members, v2);
437 : 7532787 : pe1.ssa_base = op2;
438 : 7532787 : pe1.code = r;
439 : 7532787 : pe1.members = pe2.members;
440 : 7532787 : bitmap_set_bit (pe1.members, v1);
441 : : }
442 : : }
443 : :
444 : : // Return the set of partial equivalences associated with NAME. The bitmap
445 : : // will be NULL if there are none.
446 : :
447 : : const pe_slice *
448 : 45551867 : equiv_oracle::partial_equiv_set (tree name)
449 : : {
450 : 45551867 : int v = SSA_NAME_VERSION (name);
451 : 91103734 : if (v >= (int)m_partial.length ())
452 : : return NULL;
453 : 45551867 : return &m_partial[v];
454 : : }
455 : :
456 : : // Query if there is a partial equivalence between SSA1 and SSA2. Return
457 : : // VREL_VARYING if there is not one. If BASE is non-null, return the base
458 : : // ssa-name this is a slice of.
459 : :
460 : : relation_kind
461 : 41372363 : equiv_oracle::partial_equiv (tree ssa1, tree ssa2, tree *base) const
462 : : {
463 : 41372363 : int v1 = SSA_NAME_VERSION (ssa1);
464 : 41372363 : int v2 = SSA_NAME_VERSION (ssa2);
465 : :
466 : 82744726 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
467 : : return VREL_VARYING;
468 : :
469 : 41372363 : const pe_slice &pe1 = m_partial[v1];
470 : 41372363 : const pe_slice &pe2 = m_partial[v2];
471 : 41372363 : if (pe1.members && pe2.members == pe1.members)
472 : : {
473 : 674 : if (base)
474 : 0 : *base = pe1.ssa_base;
475 : 674 : return pe_min (pe1.code, pe2.code);
476 : : }
477 : : return VREL_VARYING;
478 : : }
479 : :
480 : :
481 : : // Find and return the equivalency set for SSA along the dominators of BB.
482 : : // This is the external API.
483 : :
484 : : const_bitmap
485 : 106506817 : equiv_oracle::equiv_set (tree ssa, basic_block bb)
486 : : {
487 : : // Search the dominator tree for an equivalency.
488 : 106506817 : equiv_chain *equiv = find_equiv_dom (ssa, bb);
489 : 106506817 : if (equiv)
490 : 11029587 : return equiv->m_names;
491 : :
492 : : // Otherwise return a cached equiv set containing just this SSA.
493 : 95477230 : unsigned v = SSA_NAME_VERSION (ssa);
494 : 190954460 : if (v >= m_self_equiv.length ())
495 : 20 : m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
496 : :
497 : 95477230 : if (!m_self_equiv[v])
498 : : {
499 : 25840689 : m_self_equiv[v] = BITMAP_ALLOC (&m_bitmaps);
500 : 25840689 : bitmap_set_bit (m_self_equiv[v], v);
501 : : }
502 : 95477230 : return m_self_equiv[v];
503 : : }
504 : :
505 : : // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
506 : :
507 : : relation_kind
508 : 0 : equiv_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
509 : : {
510 : : // If the 2 ssa names share the same equiv set, they are equal.
511 : 0 : if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb))
512 : : return VREL_EQ;
513 : :
514 : : // Check if there is a partial equivalence.
515 : 0 : return partial_equiv (ssa1, ssa2);
516 : : }
517 : :
518 : : // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
519 : :
520 : : relation_kind
521 : 0 : equiv_oracle::query_relation (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1,
522 : : const_bitmap e2)
523 : : {
524 : : // If the 2 ssa names share the same equiv set, they are equal.
525 : 0 : if (bitmap_equal_p (e1, e2))
526 : 0 : return VREL_EQ;
527 : : return VREL_VARYING;
528 : : }
529 : :
530 : : // If SSA has an equivalence in block BB, find and return it.
531 : : // Otherwise return NULL.
532 : :
533 : : equiv_chain *
534 : 75740409 : equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
535 : : {
536 : 151480818 : if (bb >= (int)m_equiv.length () || !m_equiv[bb])
537 : : return NULL;
538 : :
539 : 32310958 : return m_equiv[bb]->find (ssa);
540 : : }
541 : :
542 : : // Starting at block BB, walk the dominator chain looking for the nearest
543 : : // equivalence set containing NAME.
544 : :
545 : : equiv_chain *
546 : 119496362 : equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
547 : : {
548 : 119496362 : unsigned v = SSA_NAME_VERSION (name);
549 : : // Short circuit looking for names which have no equivalences.
550 : : // Saves time looking for something which does not exist.
551 : 119496362 : if (!bitmap_bit_p (m_equiv_set, v))
552 : : return NULL;
553 : :
554 : : // NAME has at least once equivalence set, check to see if it has one along
555 : : // the dominator tree.
556 : 76712545 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
557 : : {
558 : 75740409 : equiv_chain *ptr = find_equiv_block (v, bb->index);
559 : 75740409 : if (ptr)
560 : 17986206 : return ptr;
561 : : }
562 : : return NULL;
563 : : }
564 : :
565 : : // Register equivalence between ssa_name V and set EQUIV in block BB,
566 : :
567 : : bitmap
568 : 78673 : equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
569 : : {
570 : : // V will have an equivalency now.
571 : 78673 : bitmap_set_bit (m_equiv_set, v);
572 : :
573 : : // If that equiv chain is in this block, simply use it.
574 : 78673 : if (equiv->m_bb == bb)
575 : : {
576 : 20043 : bitmap_set_bit (equiv->m_names, v);
577 : 20043 : bitmap_set_bit (m_equiv[bb->index]->m_names, v);
578 : 20043 : return NULL;
579 : : }
580 : :
581 : : // Otherwise create an equivalence for this block which is a copy
582 : : // of equiv, the add V to the set.
583 : 58630 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
584 : 58630 : valid_equivs (b, equiv->m_names, bb);
585 : 58630 : bitmap_set_bit (b, v);
586 : 58630 : return b;
587 : : }
588 : :
589 : : // Register equivalence between set equiv_1 and equiv_2 in block BB.
590 : : // Return NULL if either name can be merged with the other. Otherwise
591 : : // return a pointer to the combined bitmap of names. This allows the
592 : : // caller to do any setup required for a new element.
593 : :
594 : : bitmap
595 : 3215561 : equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
596 : : equiv_chain *equiv_2)
597 : : {
598 : : // If equiv_1 is already in BB, use it as the combined set.
599 : 3215561 : if (equiv_1->m_bb == bb)
600 : : {
601 : 1748599 : valid_equivs (equiv_1->m_names, equiv_2->m_names, bb);
602 : : // Its hard to delete from a single linked list, so
603 : : // just clear the second one.
604 : 1748599 : if (equiv_2->m_bb == bb)
605 : 167024 : bitmap_clear (equiv_2->m_names);
606 : : else
607 : : // Ensure the new names are in the summary for BB.
608 : 1581575 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
609 : 1748599 : return NULL;
610 : : }
611 : : // If equiv_2 is in BB, use it for the combined set.
612 : 1466962 : if (equiv_2->m_bb == bb)
613 : : {
614 : 2736 : valid_equivs (equiv_2->m_names, equiv_1->m_names, bb);
615 : : // Ensure the new names are in the summary.
616 : 2736 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
617 : 2736 : return NULL;
618 : : }
619 : :
620 : : // At this point, neither equivalence is from this block.
621 : 1464226 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
622 : 1464226 : valid_equivs (b, equiv_1->m_names, bb);
623 : 1464226 : valid_equivs (b, equiv_2->m_names, bb);
624 : 1464226 : return b;
625 : : }
626 : :
627 : : // Create an equivalency set containing only SSA in its definition block.
628 : : // This is done the first time SSA is registered in an equivalency and blocks
629 : : // any DOM searches past the definition.
630 : :
631 : : void
632 : 6021000 : equiv_oracle::register_initial_def (tree ssa)
633 : : {
634 : 6021000 : if (SSA_NAME_IS_DEFAULT_DEF (ssa))
635 : : return;
636 : 5932673 : basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
637 : 5932673 : gcc_checking_assert (bb && !find_equiv_dom (ssa, bb));
638 : :
639 : 5932673 : unsigned v = SSA_NAME_VERSION (ssa);
640 : 5932673 : bitmap_set_bit (m_equiv_set, v);
641 : 5932673 : bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps);
642 : 5932673 : bitmap_set_bit (equiv_set, v);
643 : 5932673 : add_equiv_to_block (bb, equiv_set);
644 : : }
645 : :
646 : : // Register an equivalence between SSA1 and SSA2 in block BB.
647 : : // The equivalence oracle maintains a vector of equivalencies indexed by basic
648 : : // block. When an equivalence between SSA1 and SSA2 is registered in block BB,
649 : : // a query is made as to what equivalences both names have already, and
650 : : // any preexisting equivalences are merged to create a single equivalence
651 : : // containing all the ssa_names in this basic block.
652 : :
653 : : void
654 : 11873645 : equiv_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
655 : : tree ssa2)
656 : : {
657 : : // Process partial equivalencies.
658 : 11873645 : if (relation_partial_equiv_p (k))
659 : : {
660 : 8345209 : add_partial_equiv (k, ssa1, ssa2);
661 : 8345209 : return;
662 : : }
663 : : // Only handle equality relations.
664 : 3528436 : if (k != VREL_EQ)
665 : : return;
666 : :
667 : 3528436 : unsigned v1 = SSA_NAME_VERSION (ssa1);
668 : 3528436 : unsigned v2 = SSA_NAME_VERSION (ssa2);
669 : :
670 : : // If this is the first time an ssa_name has an equivalency registered
671 : : // create a self-equivalency record in the def block.
672 : 3528436 : if (!bitmap_bit_p (m_equiv_set, v1))
673 : 3198238 : register_initial_def (ssa1);
674 : 3528436 : if (!bitmap_bit_p (m_equiv_set, v2))
675 : 2822762 : register_initial_def (ssa2);
676 : :
677 : 3528436 : equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
678 : 3528436 : equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
679 : :
680 : : // Check if they are the same set
681 : 3528436 : if (equiv_1 && equiv_1 == equiv_2)
682 : : return;
683 : :
684 : 3305024 : bitmap equiv_set;
685 : :
686 : : // Case where we have 2 SSA_NAMEs that are not in any set.
687 : 3305024 : if (!equiv_1 && !equiv_2)
688 : : {
689 : 10790 : bitmap_set_bit (m_equiv_set, v1);
690 : 10790 : bitmap_set_bit (m_equiv_set, v2);
691 : :
692 : 10790 : equiv_set = BITMAP_ALLOC (&m_bitmaps);
693 : 10790 : bitmap_set_bit (equiv_set, v1);
694 : 10790 : bitmap_set_bit (equiv_set, v2);
695 : : }
696 : 3294234 : else if (!equiv_1 && equiv_2)
697 : 23048 : equiv_set = register_equiv (bb, v1, equiv_2);
698 : 3271186 : else if (equiv_1 && !equiv_2)
699 : 55625 : equiv_set = register_equiv (bb, v2, equiv_1);
700 : : else
701 : 3215561 : equiv_set = register_equiv (bb, equiv_1, equiv_2);
702 : :
703 : : // A non-null return is a bitmap that is to be added to the current
704 : : // block as a new equivalence.
705 : 3305024 : if (!equiv_set)
706 : : return;
707 : :
708 : 1533646 : add_equiv_to_block (bb, equiv_set);
709 : : }
710 : :
711 : : // Add an equivalency record in block BB containing bitmap EQUIV_SET.
712 : : // Note the internal caller is responsible for allocating EQUIV_SET properly.
713 : :
714 : : void
715 : 7466319 : equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
716 : : {
717 : 7466319 : equiv_chain *ptr;
718 : :
719 : : // Check if this is the first time a block has an equivalence added.
720 : : // and create a header block. And set the summary for this block.
721 : 7466319 : limit_check (bb);
722 : 7466319 : if (!m_equiv[bb->index])
723 : : {
724 : 4775993 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
725 : : sizeof (equiv_chain));
726 : 4775993 : ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
727 : 4775993 : bitmap_copy (ptr->m_names, equiv_set);
728 : 4775993 : ptr->m_bb = bb;
729 : 4775993 : ptr->m_next = NULL;
730 : 4775993 : m_equiv[bb->index] = ptr;
731 : : }
732 : :
733 : : // Now create the element for this equiv set and initialize it.
734 : 7466319 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
735 : 7466319 : ptr->m_names = equiv_set;
736 : 7466319 : ptr->m_bb = bb;
737 : 14932638 : gcc_checking_assert (bb->index < (int)m_equiv.length ());
738 : 7466319 : ptr->m_next = m_equiv[bb->index]->m_next;
739 : 7466319 : m_equiv[bb->index]->m_next = ptr;
740 : 7466319 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
741 : 7466319 : }
742 : :
743 : : // Make sure the BB vector is big enough and grow it if needed.
744 : :
745 : : void
746 : 7466319 : equiv_oracle::limit_check (basic_block bb)
747 : : {
748 : 7466319 : int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
749 : 14932638 : if (i >= (int)m_equiv.length ())
750 : 1 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
751 : 7466319 : }
752 : :
753 : : // Dump the equivalence sets in BB to file F.
754 : :
755 : : void
756 : 259 : equiv_oracle::dump (FILE *f, basic_block bb) const
757 : : {
758 : 518 : if (bb->index >= (int)m_equiv.length ())
759 : : return;
760 : : // Process equivalences.
761 : 259 : if (m_equiv[bb->index])
762 : : {
763 : 10 : equiv_chain *ptr = m_equiv[bb->index]->m_next;
764 : 21 : for (; ptr; ptr = ptr->m_next)
765 : 11 : ptr->dump (f);
766 : : }
767 : : // Look for partial equivalences defined in this block..
768 : 28010 : for (unsigned i = 0; i < num_ssa_names; i++)
769 : : {
770 : 13746 : tree name = ssa_name (i);
771 : 19216 : if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name))
772 : 8276 : continue;
773 : 10940 : if (i >= m_partial.length ())
774 : : break;
775 : 5470 : tree base = m_partial[i].ssa_base;
776 : 5470 : if (base && name != base && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb)
777 : : {
778 : 40 : relation_kind k = partial_equiv (name, base);
779 : 40 : if (k != VREL_VARYING)
780 : : {
781 : 40 : value_relation vr (k, name, base);
782 : 40 : fprintf (f, "Partial equiv ");
783 : 40 : vr.dump (f);
784 : 40 : fputc ('\n',f);
785 : : }
786 : : }
787 : : }
788 : : }
789 : :
790 : : // Dump all equivalence sets known to the oracle.
791 : :
792 : : void
793 : 0 : equiv_oracle::dump (FILE *f) const
794 : : {
795 : 0 : fprintf (f, "Equivalency dump\n");
796 : 0 : for (unsigned i = 0; i < m_equiv.length (); i++)
797 : 0 : if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
798 : : {
799 : 0 : fprintf (f, "BB%d\n", i);
800 : 0 : dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
801 : : }
802 : 0 : }
803 : :
804 : :
805 : : // --------------------------------------------------------------------------
806 : : // Negate the current relation.
807 : :
808 : : void
809 : 0 : value_relation::negate ()
810 : : {
811 : 0 : related = relation_negate (related);
812 : 0 : }
813 : :
814 : : // Perform an intersection between 2 relations. *this &&= p.
815 : :
816 : : bool
817 : 2707271 : value_relation::intersect (value_relation &p)
818 : : {
819 : : // Save previous value
820 : 2707271 : relation_kind old = related;
821 : :
822 : 2707271 : if (p.op1 () == op1 () && p.op2 () == op2 ())
823 : 2707133 : related = relation_intersect (kind (), p.kind ());
824 : 138 : else if (p.op2 () == op1 () && p.op1 () == op2 ())
825 : 138 : related = relation_intersect (kind (), relation_swap (p.kind ()));
826 : : else
827 : : return false;
828 : :
829 : 2707271 : return old != related;
830 : : }
831 : :
832 : : // Perform a union between 2 relations. *this ||= p.
833 : :
834 : : bool
835 : 0 : value_relation::union_ (value_relation &p)
836 : : {
837 : : // Save previous value
838 : 0 : relation_kind old = related;
839 : :
840 : 0 : if (p.op1 () == op1 () && p.op2 () == op2 ())
841 : 0 : related = relation_union (kind(), p.kind());
842 : 0 : else if (p.op2 () == op1 () && p.op1 () == op2 ())
843 : 0 : related = relation_union (kind(), relation_swap (p.kind ()));
844 : : else
845 : : return false;
846 : :
847 : 0 : return old != related;
848 : : }
849 : :
850 : : // Identify and apply any transitive relations between REL
851 : : // and THIS. Return true if there was a transformation.
852 : :
853 : : bool
854 : 9732201 : value_relation::apply_transitive (const value_relation &rel)
855 : : {
856 : 9732201 : relation_kind k = VREL_VARYING;
857 : :
858 : : // Identify any common operand, and normalize the relations to
859 : : // the form : A < B B < C produces A < C
860 : 9732201 : if (rel.op1 () == name2)
861 : : {
862 : : // A < B B < C
863 : 1948982 : if (rel.op2 () == name1)
864 : : return false;
865 : 1866127 : k = relation_transitive (kind (), rel.kind ());
866 : 1866127 : if (k != VREL_VARYING)
867 : : {
868 : 588837 : related = k;
869 : 588837 : name2 = rel.op2 ();
870 : 588837 : return true;
871 : : }
872 : : }
873 : 7783219 : else if (rel.op1 () == name1)
874 : : {
875 : : // B > A B < C
876 : 4990494 : if (rel.op2 () == name2)
877 : : return false;
878 : 1605481 : k = relation_transitive (relation_swap (kind ()), rel.kind ());
879 : 1605481 : if (k != VREL_VARYING)
880 : : {
881 : 364118 : related = k;
882 : 364118 : name1 = name2;
883 : 364118 : name2 = rel.op2 ();
884 : 364118 : return true;
885 : : }
886 : : }
887 : 2792725 : else if (rel.op2 () == name2)
888 : : {
889 : : // A < B C > B
890 : 2091952 : if (rel.op1 () == name1)
891 : : return false;
892 : 2091952 : k = relation_transitive (kind (), relation_swap (rel.kind ()));
893 : 2091952 : if (k != VREL_VARYING)
894 : : {
895 : 464015 : related = k;
896 : 464015 : name2 = rel.op1 ();
897 : 464015 : return true;
898 : : }
899 : : }
900 : 700773 : else if (rel.op2 () == name1)
901 : : {
902 : : // B > A C > B
903 : 700773 : if (rel.op1 () == name2)
904 : : return false;
905 : 700773 : k = relation_transitive (relation_swap (kind ()),
906 : : relation_swap (rel.kind ()));
907 : 700773 : if (k != VREL_VARYING)
908 : : {
909 : 222206 : related = k;
910 : 222206 : name1 = name2;
911 : 222206 : name2 = rel.op1 ();
912 : 222206 : return true;
913 : : }
914 : : }
915 : : return false;
916 : : }
917 : :
918 : : // Create a trio from this value relation given LHS, OP1 and OP2.
919 : :
920 : : relation_trio
921 : 34630176 : value_relation::create_trio (tree lhs, tree op1, tree op2)
922 : : {
923 : 34630176 : relation_kind lhs_1;
924 : 34630176 : if (lhs == name1 && op1 == name2)
925 : 80400 : lhs_1 = related;
926 : 34549776 : else if (lhs == name2 && op1 == name1)
927 : 93335 : lhs_1 = relation_swap (related);
928 : : else
929 : : lhs_1 = VREL_VARYING;
930 : :
931 : 34630176 : relation_kind lhs_2;
932 : 34630176 : if (lhs == name1 && op2 == name2)
933 : 47427 : lhs_2 = related;
934 : 34582749 : else if (lhs == name2 && op2 == name1)
935 : 134011 : lhs_2 = relation_swap (related);
936 : : else
937 : : lhs_2 = VREL_VARYING;
938 : :
939 : 34630176 : relation_kind op_op;
940 : 34630176 : if (op1 == name1 && op2 == name2)
941 : 24932995 : op_op = related;
942 : 9697181 : else if (op1 == name2 && op2 == name1)
943 : 0 : op_op = relation_swap (related);
944 : 9697181 : else if (op1 == op2)
945 : : op_op = VREL_EQ;
946 : : else
947 : 9687360 : op_op = VREL_VARYING;
948 : :
949 : 34630176 : return relation_trio (lhs_1, lhs_2, op_op);
950 : : }
951 : :
952 : : // Dump the relation to file F.
953 : :
954 : : void
955 : 1045 : value_relation::dump (FILE *f) const
956 : : {
957 : 1045 : if (!name1 || !name2)
958 : : {
959 : 0 : fprintf (f, "no relation registered");
960 : 0 : return;
961 : : }
962 : 1045 : fputc ('(', f);
963 : 1045 : print_generic_expr (f, op1 (), TDF_SLIM);
964 : 1045 : print_relation (f, kind ());
965 : 1045 : print_generic_expr (f, op2 (), TDF_SLIM);
966 : 1045 : fputc(')', f);
967 : : }
968 : :
969 : : // This container is used to link relations in a chain.
970 : :
971 : : class relation_chain : public value_relation
972 : : {
973 : : public:
974 : : relation_chain *m_next;
975 : : };
976 : :
977 : : // ------------------------------------------------------------------------
978 : :
979 : : // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
980 : : // This will allow equivalencies to be applied to any SSA_NAME in a relation.
981 : :
982 : : relation_kind
983 : 140568826 : relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
984 : : {
985 : 140568826 : if (!m_names)
986 : : return VREL_VARYING;
987 : :
988 : : // If both b1 and b2 aren't referenced in this block, cant be a relation
989 : 99748230 : if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
990 : 96383873 : return VREL_VARYING;
991 : :
992 : : // Search for the first relation that contains BOTH an element from B1
993 : : // and B2, and return that relation.
994 : 10721179 : for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
995 : : {
996 : 9487100 : unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
997 : 9487100 : unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
998 : 9487100 : if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
999 : 1996676 : return ptr->kind ();
1000 : 7490424 : if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
1001 : 133602 : return relation_swap (ptr->kind ());
1002 : : }
1003 : :
1004 : : return VREL_VARYING;
1005 : : }
1006 : :
1007 : : // Instantiate a relation oracle.
1008 : :
1009 : 23395808 : dom_oracle::dom_oracle ()
1010 : : {
1011 : 23395808 : m_relations.create (0);
1012 : 23395808 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1013 : 23395808 : m_relation_set = BITMAP_ALLOC (&m_bitmaps);
1014 : 23395808 : m_tmp = BITMAP_ALLOC (&m_bitmaps);
1015 : 23395808 : m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
1016 : 23395808 : }
1017 : :
1018 : : // Destruct a relation oracle.
1019 : :
1020 : 46791616 : dom_oracle::~dom_oracle ()
1021 : : {
1022 : 23395808 : m_relations.release ();
1023 : 46791616 : }
1024 : :
1025 : : // Register relation K between ssa_name OP1 and OP2 on STMT.
1026 : :
1027 : : void
1028 : 21847008 : relation_oracle::register_stmt (gimple *stmt, relation_kind k, tree op1,
1029 : : tree op2)
1030 : : {
1031 : 21847008 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1032 : 21847008 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1033 : 21847008 : gcc_checking_assert (stmt && gimple_bb (stmt));
1034 : :
1035 : : // Don't register lack of a relation.
1036 : 21847008 : if (k == VREL_VARYING)
1037 : : return;
1038 : :
1039 : 21847008 : if (dump_file && (dump_flags & TDF_DETAILS))
1040 : : {
1041 : 444 : value_relation vr (k, op1, op2);
1042 : 444 : fprintf (dump_file, " Registering value_relation ");
1043 : 444 : vr.dump (dump_file);
1044 : 444 : fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
1045 : 444 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1046 : : }
1047 : :
1048 : : // If an equivalence is being added between a PHI and one of its arguments
1049 : : // make sure that that argument is not defined in the same block.
1050 : : // This can happen along back edges and the equivalence will not be
1051 : : // applicable as it would require a use before def.
1052 : 21847008 : if (k == VREL_EQ && is_a<gphi *> (stmt))
1053 : : {
1054 : 1776077 : tree phi_def = gimple_phi_result (stmt);
1055 : 1776077 : gcc_checking_assert (phi_def == op1 || phi_def == op2);
1056 : 1776077 : tree arg = op2;
1057 : 1776077 : if (phi_def == op2)
1058 : 0 : arg = op1;
1059 : 1776077 : if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
1060 : : {
1061 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1062 : : {
1063 : 0 : fprintf (dump_file, " Not registered due to ");
1064 : 0 : print_generic_expr (dump_file, arg, TDF_SLIM);
1065 : 0 : fprintf (dump_file, " being defined in the same block.\n");
1066 : : }
1067 : 0 : return;
1068 : : }
1069 : : }
1070 : 21847008 : register_relation (gimple_bb (stmt), k, op1, op2);
1071 : : }
1072 : :
1073 : : // Register relation K between ssa_name OP1 and OP2 on edge E.
1074 : :
1075 : : void
1076 : 5544237 : relation_oracle::register_edge (edge e, relation_kind k, tree op1, tree op2)
1077 : : {
1078 : 5544237 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1079 : 5544237 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1080 : :
1081 : : // Do not register lack of relation, or blocks which have more than
1082 : : // edge E for a predecessor.
1083 : 11088474 : if (k == VREL_VARYING || !single_pred_p (e->dest))
1084 : : return;
1085 : :
1086 : 5544237 : if (dump_file && (dump_flags & TDF_DETAILS))
1087 : : {
1088 : 113 : value_relation vr (k, op1, op2);
1089 : 113 : fprintf (dump_file, " Registering value_relation ");
1090 : 113 : vr.dump (dump_file);
1091 : 113 : fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
1092 : : }
1093 : :
1094 : 5544237 : register_relation (e->dest, k, op1, op2);
1095 : : }
1096 : :
1097 : : // Register relation K between OP! and OP2 in block BB.
1098 : : // This creates the record and searches for existing records in the dominator
1099 : : // tree to merge with.
1100 : :
1101 : : void
1102 : 27391245 : dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
1103 : : tree op2)
1104 : : {
1105 : : // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1106 : : // and no other relation makes sense.
1107 : 27391245 : if (op1 == op2)
1108 : : return;
1109 : :
1110 : : // Equivalencies are handled by the equivalence oracle.
1111 : 27384500 : if (relation_equiv_p (k))
1112 : 11873645 : equiv_oracle::register_relation (bb, k, op1, op2);
1113 : : else
1114 : : {
1115 : : // if neither op1 nor op2 are in a relation before this is registered,
1116 : : // there will be no transitive.
1117 : 15510855 : bool check = bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op1))
1118 : 26019954 : || bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op2));
1119 : 15510855 : relation_chain *ptr = set_one_relation (bb, k, op1, op2);
1120 : 15510855 : if (ptr && check)
1121 : 4377118 : register_transitives (bb, *ptr);
1122 : : }
1123 : : }
1124 : :
1125 : : // Register relation K between OP! and OP2 in block BB.
1126 : : // This creates the record and searches for existing records in the dominator
1127 : : // tree to merge with. Return the record, or NULL if no record was created.
1128 : :
1129 : : relation_chain *
1130 : 17150031 : dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1,
1131 : : tree op2)
1132 : : {
1133 : 17150031 : gcc_checking_assert (k != VREL_VARYING && k != VREL_EQ);
1134 : :
1135 : 17150031 : value_relation vr(k, op1, op2);
1136 : 17150031 : int bbi = bb->index;
1137 : :
1138 : 34300062 : if (bbi >= (int)m_relations.length())
1139 : 3 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1140 : :
1141 : : // Summary bitmap indicating what ssa_names have relations in this BB.
1142 : 17150031 : bitmap bm = m_relations[bbi].m_names;
1143 : 17150031 : if (!bm)
1144 : 9846200 : bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
1145 : 17150031 : unsigned v1 = SSA_NAME_VERSION (op1);
1146 : 17150031 : unsigned v2 = SSA_NAME_VERSION (op2);
1147 : :
1148 : 17150031 : relation_kind curr;
1149 : 17150031 : relation_chain *ptr;
1150 : 17150031 : curr = find_relation_block (bbi, v1, v2, &ptr);
1151 : : // There is an existing relation in this block, just intersect with it.
1152 : 17150031 : if (curr != VREL_VARYING)
1153 : : {
1154 : 2707271 : if (dump_file && (dump_flags & TDF_DETAILS))
1155 : : {
1156 : 16 : fprintf (dump_file, " Intersecting with existing ");
1157 : 16 : ptr->dump (dump_file);
1158 : : }
1159 : : // Check into whether we can simply replace the relation rather than
1160 : : // intersecting it. This may help with some optimistic iterative
1161 : : // updating algorithms.
1162 : 2707271 : bool new_rel = ptr->intersect (vr);
1163 : 2707271 : if (dump_file && (dump_flags & TDF_DETAILS))
1164 : : {
1165 : 16 : fprintf (dump_file, " to produce ");
1166 : 16 : ptr->dump (dump_file);
1167 : 28 : fprintf (dump_file, " %s.\n", new_rel ? "Updated" : "No Change");
1168 : : }
1169 : : // If there was no change, return no record..
1170 : 2707271 : if (!new_rel)
1171 : : return NULL;
1172 : : }
1173 : : else
1174 : : {
1175 : 14442760 : if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
1176 : : {
1177 : 86026 : if (dump_file && (dump_flags & TDF_DETAILS))
1178 : 0 : fprintf (dump_file, " Not registered due to bb being full\n");
1179 : 86026 : return NULL;
1180 : : }
1181 : 14356734 : m_relations[bbi].m_num_relations++;
1182 : : // Check for an existing relation further up the DOM chain.
1183 : : // By including dominating relations, The first one found in any search
1184 : : // will be the aggregate of all the previous ones.
1185 : 14356734 : curr = find_relation_dom (bb, v1, v2);
1186 : 14356734 : if (curr != VREL_VARYING)
1187 : 636576 : k = relation_intersect (curr, k);
1188 : :
1189 : 14356734 : bitmap_set_bit (bm, v1);
1190 : 14356734 : bitmap_set_bit (bm, v2);
1191 : 14356734 : bitmap_set_bit (m_relation_set, v1);
1192 : 14356734 : bitmap_set_bit (m_relation_set, v2);
1193 : :
1194 : 14356734 : ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1195 : : sizeof (relation_chain));
1196 : 14356734 : ptr->set_relation (k, op1, op2);
1197 : 14356734 : ptr->m_next = m_relations[bbi].m_head;
1198 : 14356734 : m_relations[bbi].m_head = ptr;
1199 : : }
1200 : 14527556 : return ptr;
1201 : : }
1202 : :
1203 : : // Starting at ROOT_BB search the DOM tree looking for relations which
1204 : : // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
1205 : : // bitmaps for op1/op2 and any of their equivalences that should also be
1206 : : // considered.
1207 : :
1208 : : void
1209 : 4377118 : dom_oracle::register_transitives (basic_block root_bb,
1210 : : const value_relation &relation)
1211 : : {
1212 : 4377118 : basic_block bb;
1213 : : // Only apply transitives to certain kinds of operations.
1214 : 4377118 : switch (relation.kind ())
1215 : : {
1216 : 3245992 : case VREL_LE:
1217 : 3245992 : case VREL_LT:
1218 : 3245992 : case VREL_GT:
1219 : 3245992 : case VREL_GE:
1220 : 3245992 : break;
1221 : : default:
1222 : : return;
1223 : : }
1224 : :
1225 : 3245992 : const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb);
1226 : 3245992 : const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb);
1227 : :
1228 : 69626345 : for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1229 : : {
1230 : 66455692 : int bbi = bb->index;
1231 : 132911384 : if (bbi >= (int)m_relations.length())
1232 : 0 : continue;
1233 : 66455692 : const_bitmap bm = m_relations[bbi].m_names;
1234 : 66455692 : if (!bm)
1235 : 44712131 : continue;
1236 : 21743561 : if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
1237 : 15386814 : continue;
1238 : : // At least one of the 2 ops has a relation in this block.
1239 : 6356747 : relation_chain *ptr;
1240 : 32751701 : for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
1241 : : {
1242 : : // In the presence of an equivalence, 2 operands may do not
1243 : : // naturally match. ie with equivalence a_2 == b_3
1244 : : // given c_1 < a_2 && b_3 < d_4
1245 : : // convert the second relation (b_3 < d_4) to match any
1246 : : // equivalences to found in the first relation.
1247 : : // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1248 : : // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1249 : :
1250 : 26470293 : tree r1, r2;
1251 : 26470293 : tree p1 = ptr->op1 ();
1252 : 26470293 : tree p2 = ptr->op2 ();
1253 : : // Find which equivalence is in the first operand.
1254 : 26470293 : if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
1255 : : r1 = p1;
1256 : 21479238 : else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
1257 : : r1 = p2;
1258 : : else
1259 : 20695442 : r1 = NULL_TREE;
1260 : :
1261 : : // Find which equivalence is in the second operand.
1262 : 26470293 : if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
1263 : : r2 = p1;
1264 : 24520750 : else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
1265 : : r2 = p2;
1266 : : else
1267 : 19043617 : r2 = NULL_TREE;
1268 : :
1269 : : // Ignore if both NULL (not relevant relation) or the same,
1270 : 26470293 : if (r1 == r2)
1271 : 16738092 : continue;
1272 : :
1273 : : // Any operand not an equivalence, just take the real operand.
1274 : 9732201 : if (!r1)
1275 : 3958079 : r1 = relation.op1 ();
1276 : 9732201 : if (!r2)
1277 : 2306254 : r2 = relation.op2 ();
1278 : :
1279 : 9732201 : value_relation nr (relation.kind (), r1, r2);
1280 : 9732201 : if (nr.apply_transitive (*ptr))
1281 : : {
1282 : 1639176 : if (!set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ()))
1283 : 75339 : return;
1284 : 1563837 : if (dump_file && (dump_flags & TDF_DETAILS))
1285 : : {
1286 : 2 : fprintf (dump_file, " Registering transitive relation ");
1287 : 2 : nr.dump (dump_file);
1288 : 2 : fputc ('\n', dump_file);
1289 : : }
1290 : : }
1291 : :
1292 : : }
1293 : : }
1294 : : }
1295 : :
1296 : : // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1297 : : // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1298 : :
1299 : : relation_kind
1300 : 101131406 : dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
1301 : : const_bitmap b2) const
1302 : : {
1303 : 202262812 : if (bb >= m_relations.length())
1304 : : return VREL_VARYING;
1305 : :
1306 : 101131406 : return m_relations[bb].find_relation (b1, b2);
1307 : : }
1308 : :
1309 : : // Search the DOM tree for a relation between an element of equivalency set B1
1310 : : // and B2, starting with block BB.
1311 : :
1312 : : relation_kind
1313 : 10251610 : dom_oracle::query_relation (basic_block bb, const_bitmap b1,
1314 : : const_bitmap b2)
1315 : : {
1316 : 10251610 : relation_kind r;
1317 : 10251610 : if (bitmap_equal_p (b1, b2))
1318 : : return VREL_EQ;
1319 : :
1320 : : // If either name does not occur in a relation anywhere, there isn't one.
1321 : 10251610 : if (!bitmap_intersect_p (m_relation_set, b1)
1322 : 10251610 : || !bitmap_intersect_p (m_relation_set, b2))
1323 : 6939931 : return VREL_VARYING;
1324 : :
1325 : : // Search each block in the DOM tree checking.
1326 : 103897076 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1327 : : {
1328 : 101131406 : r = find_relation_block (bb->index, b1, b2);
1329 : 101131406 : if (r != VREL_VARYING)
1330 : 546009 : return r;
1331 : : }
1332 : : return VREL_VARYING;
1333 : :
1334 : : }
1335 : :
1336 : : // Find a relation in block BB between ssa version V1 and V2. If a relation
1337 : : // is found, return a pointer to the chain object in OBJ.
1338 : :
1339 : : relation_kind
1340 : 393485452 : dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
1341 : : relation_chain **obj) const
1342 : : {
1343 : 786970904 : if (bb >= (int)m_relations.length())
1344 : : return VREL_VARYING;
1345 : :
1346 : 393485452 : const_bitmap bm = m_relations[bb].m_names;
1347 : 393485452 : if (!bm)
1348 : : return VREL_VARYING;
1349 : :
1350 : : // If both b1 and b2 aren't referenced in this block, cant be a relation
1351 : 335780995 : if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1352 : 326017987 : return VREL_VARYING;
1353 : :
1354 : 9763008 : relation_chain *ptr;
1355 : 63180349 : for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1356 : : {
1357 : 60893555 : unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1358 : 60893555 : unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1359 : 60893555 : if (v1 == op1 && v2 == op2)
1360 : : {
1361 : 7235935 : if (obj)
1362 : 2707133 : *obj = ptr;
1363 : 7235935 : return ptr->kind ();
1364 : : }
1365 : 53657620 : if (v1 == op2 && v2 == op1)
1366 : : {
1367 : 240279 : if (obj)
1368 : 138 : *obj = ptr;
1369 : 240279 : return relation_swap (ptr->kind ());
1370 : : }
1371 : : }
1372 : :
1373 : : return VREL_VARYING;
1374 : : }
1375 : :
1376 : : // Find a relation between SSA version V1 and V2 in the dominator tree
1377 : : // starting with block BB
1378 : :
1379 : : relation_kind
1380 : 20408010 : dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const
1381 : : {
1382 : 20408010 : relation_kind r;
1383 : : // IF either name does not occur in a relation anywhere, there isn't one.
1384 : 20408010 : if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1385 : 11676478 : return VREL_VARYING;
1386 : :
1387 : 380298010 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1388 : : {
1389 : 376335421 : r = find_relation_block (bb->index, v1, v2);
1390 : 376335421 : if (r != VREL_VARYING)
1391 : 4768943 : return r;
1392 : : }
1393 : : return VREL_VARYING;
1394 : :
1395 : : }
1396 : :
1397 : : // Query if there is a relation between SSA1 and SS2 in block BB or a
1398 : : // dominator of BB
1399 : :
1400 : : relation_kind
1401 : 41667290 : dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1402 : : {
1403 : 41667290 : relation_kind kind;
1404 : 41667290 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1405 : 41667290 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1406 : 41667290 : if (v1 == v2)
1407 : : return VREL_EQ;
1408 : :
1409 : : // If v1 or v2 do not have any relations or equivalences, a partial
1410 : : // equivalence is the only possibility.
1411 : 72781063 : if ((!bitmap_bit_p (m_relation_set, v1) && !has_equiv_p (v1))
1412 : 43604046 : || (!bitmap_bit_p (m_relation_set, v2) && !has_equiv_p (v2)))
1413 : 35320974 : return partial_equiv (ssa1, ssa2);
1414 : :
1415 : : // Check for equivalence first. They must be in each equivalency set.
1416 : 6258832 : const_bitmap equiv1 = equiv_set (ssa1, bb);
1417 : 6258832 : const_bitmap equiv2 = equiv_set (ssa2, bb);
1418 : 6258832 : if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
1419 : : return VREL_EQ;
1420 : :
1421 : 6051349 : kind = partial_equiv (ssa1, ssa2);
1422 : 6051349 : if (kind != VREL_VARYING)
1423 : : return kind;
1424 : :
1425 : : // Initially look for a direct relationship and just return that.
1426 : 6051276 : kind = find_relation_dom (bb, v1, v2);
1427 : 6051276 : if (kind != VREL_VARYING)
1428 : : return kind;
1429 : :
1430 : : // Query using the equivalence sets.
1431 : 1918909 : kind = query_relation (bb, equiv1, equiv2);
1432 : 1918909 : return kind;
1433 : : }
1434 : :
1435 : : // Dump all the relations in block BB to file F.
1436 : :
1437 : : void
1438 : 259 : dom_oracle::dump (FILE *f, basic_block bb) const
1439 : : {
1440 : 259 : equiv_oracle::dump (f,bb);
1441 : :
1442 : 518 : if (bb->index >= (int)m_relations.length ())
1443 : : return;
1444 : 259 : if (!m_relations[bb->index].m_names)
1445 : : return;
1446 : :
1447 : 37 : relation_chain *ptr = m_relations[bb->index].m_head;
1448 : 84 : for (; ptr; ptr = ptr->m_next)
1449 : : {
1450 : 47 : fprintf (f, "Relational : ");
1451 : 47 : ptr->dump (f);
1452 : 47 : fprintf (f, "\n");
1453 : : }
1454 : : }
1455 : :
1456 : : // Dump all the relations known to file F.
1457 : :
1458 : : void
1459 : 0 : dom_oracle::dump (FILE *f) const
1460 : : {
1461 : 0 : fprintf (f, "Relation dump\n");
1462 : 0 : for (unsigned i = 0; i < m_relations.length (); i++)
1463 : 0 : if (BASIC_BLOCK_FOR_FN (cfun, i))
1464 : : {
1465 : 0 : fprintf (f, "BB%d\n", i);
1466 : 0 : dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
1467 : : }
1468 : 0 : }
1469 : :
1470 : : void
1471 : 0 : relation_oracle::debug () const
1472 : : {
1473 : 0 : dump (stderr);
1474 : 0 : }
1475 : :
1476 : 23218043 : path_oracle::path_oracle (relation_oracle *oracle)
1477 : : {
1478 : 23218043 : set_root_oracle (oracle);
1479 : 23218043 : bitmap_obstack_initialize (&m_bitmaps);
1480 : 23218043 : obstack_init (&m_chain_obstack);
1481 : :
1482 : : // Initialize header records.
1483 : 23218043 : m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
1484 : 23218043 : m_equiv.m_bb = NULL;
1485 : 23218043 : m_equiv.m_next = NULL;
1486 : 23218043 : m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
1487 : 23218043 : m_relations.m_head = NULL;
1488 : 23218043 : m_killed_defs = BITMAP_ALLOC (&m_bitmaps);
1489 : 23218043 : }
1490 : :
1491 : 46436086 : path_oracle::~path_oracle ()
1492 : : {
1493 : 23218043 : obstack_free (&m_chain_obstack, NULL);
1494 : 23218043 : bitmap_obstack_release (&m_bitmaps);
1495 : 46436086 : }
1496 : :
1497 : : // Return the equiv set for SSA, and if there isn't one, check for equivs
1498 : : // starting in block BB.
1499 : :
1500 : : const_bitmap
1501 : 106203774 : path_oracle::equiv_set (tree ssa, basic_block bb)
1502 : : {
1503 : : // Check the list first.
1504 : 106203774 : equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
1505 : 106203774 : if (ptr)
1506 : 58831619 : return ptr->m_names;
1507 : :
1508 : : // Otherwise defer to the root oracle.
1509 : 47372155 : if (m_root)
1510 : 42591942 : return m_root->equiv_set (ssa, bb);
1511 : :
1512 : : // Allocate a throw away bitmap if there isn't a root oracle.
1513 : 4780213 : bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
1514 : 4780213 : bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
1515 : 4780213 : return tmp;
1516 : : }
1517 : :
1518 : : // Register an equivalence between SSA1 and SSA2 resolving unknowns from
1519 : : // block BB.
1520 : :
1521 : : void
1522 : 6449299 : path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
1523 : : {
1524 : 6449299 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
1525 : 6449299 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
1526 : :
1527 : : // Check if they are the same set, if so, we're done.
1528 : 6449299 : if (bitmap_equal_p (equiv_1, equiv_2))
1529 : : return;
1530 : :
1531 : : // Don't mess around, simply create a new record and insert it first.
1532 : 6440410 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
1533 : 6440410 : valid_equivs (b, equiv_1, bb);
1534 : 6440410 : valid_equivs (b, equiv_2, bb);
1535 : :
1536 : 6440410 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1537 : : sizeof (equiv_chain));
1538 : 6440410 : ptr->m_names = b;
1539 : 6440410 : ptr->m_bb = NULL;
1540 : 6440410 : ptr->m_next = m_equiv.m_next;
1541 : 6440410 : m_equiv.m_next = ptr;
1542 : 6440410 : bitmap_ior_into (m_equiv.m_names, b);
1543 : : }
1544 : :
1545 : : // Register killing definition of an SSA_NAME.
1546 : :
1547 : : void
1548 : 48365943 : path_oracle::killing_def (tree ssa)
1549 : : {
1550 : 48365943 : if (dump_file && (dump_flags & TDF_DETAILS))
1551 : : {
1552 : 1117 : fprintf (dump_file, " Registering killing_def (path_oracle) ");
1553 : 1117 : print_generic_expr (dump_file, ssa, TDF_SLIM);
1554 : 1117 : fprintf (dump_file, "\n");
1555 : : }
1556 : :
1557 : 48365943 : unsigned v = SSA_NAME_VERSION (ssa);
1558 : :
1559 : 48365943 : bitmap_set_bit (m_killed_defs, v);
1560 : 48365943 : bitmap_set_bit (m_equiv.m_names, v);
1561 : :
1562 : : // Now add an equivalency with itself so we don't look to the root oracle.
1563 : 48365943 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
1564 : 48365943 : bitmap_set_bit (b, v);
1565 : 48365943 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1566 : : sizeof (equiv_chain));
1567 : 48365943 : ptr->m_names = b;
1568 : 48365943 : ptr->m_bb = NULL;
1569 : 48365943 : ptr->m_next = m_equiv.m_next;
1570 : 48365943 : m_equiv.m_next = ptr;
1571 : :
1572 : : // Walk the relation list and remove SSA from any relations.
1573 : 48365943 : if (!bitmap_bit_p (m_relations.m_names, v))
1574 : : return;
1575 : :
1576 : 102595 : bitmap_clear_bit (m_relations.m_names, v);
1577 : 102595 : relation_chain **prev = &(m_relations.m_head);
1578 : 102595 : relation_chain *next = NULL;
1579 : 361097 : for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
1580 : : {
1581 : 258502 : gcc_checking_assert (*prev == ptr);
1582 : 258502 : next = ptr->m_next;
1583 : 258502 : if (SSA_NAME_VERSION (ptr->op1 ()) == v
1584 : 258502 : || SSA_NAME_VERSION (ptr->op2 ()) == v)
1585 : 100961 : *prev = ptr->m_next;
1586 : : else
1587 : 157541 : prev = &(ptr->m_next);
1588 : : }
1589 : : }
1590 : :
1591 : : // Register relation K between SSA1 and SSA2, resolving unknowns by
1592 : : // querying from BB.
1593 : :
1594 : : void
1595 : 21585810 : path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
1596 : : tree ssa2)
1597 : : {
1598 : : // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1599 : : // and no other relation makes sense.
1600 : 21585810 : if (ssa1 == ssa2)
1601 : : return;
1602 : :
1603 : 21573810 : if (dump_file && (dump_flags & TDF_DETAILS))
1604 : : {
1605 : 367 : value_relation vr (k, ssa1, ssa2);
1606 : 367 : fprintf (dump_file, " Registering value_relation (path_oracle) ");
1607 : 367 : vr.dump (dump_file);
1608 : 367 : fprintf (dump_file, " (root: bb%d)\n", bb->index);
1609 : : }
1610 : :
1611 : 21573810 : relation_kind curr = query_relation (bb, ssa1, ssa2);
1612 : 21573810 : if (curr != VREL_VARYING)
1613 : 1660331 : k = relation_intersect (curr, k);
1614 : :
1615 : 21573810 : if (k == VREL_EQ)
1616 : : {
1617 : 6449299 : register_equiv (bb, ssa1, ssa2);
1618 : 6449299 : return;
1619 : : }
1620 : :
1621 : 15124511 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
1622 : 15124511 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
1623 : 15124511 : relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1624 : : sizeof (relation_chain));
1625 : 15124511 : ptr->set_relation (k, ssa1, ssa2);
1626 : 15124511 : ptr->m_next = m_relations.m_head;
1627 : 15124511 : m_relations.m_head = ptr;
1628 : : }
1629 : :
1630 : : // Query for a relationship between equiv set B1 and B2, resolving unknowns
1631 : : // starting at block BB.
1632 : :
1633 : : relation_kind
1634 : 39437420 : path_oracle::query_relation (basic_block bb, const_bitmap b1, const_bitmap b2)
1635 : : {
1636 : 39437420 : if (bitmap_equal_p (b1, b2))
1637 : : return VREL_EQ;
1638 : :
1639 : 39437420 : relation_kind k = m_relations.find_relation (b1, b2);
1640 : :
1641 : : // Do not look at the root oracle for names that have been killed
1642 : : // along the path.
1643 : 39437420 : if (bitmap_intersect_p (m_killed_defs, b1)
1644 : 39437420 : || bitmap_intersect_p (m_killed_defs, b2))
1645 : 29287344 : return k;
1646 : :
1647 : 10150076 : if (k == VREL_VARYING && m_root)
1648 : 8332701 : k = m_root->query_relation (bb, b1, b2);
1649 : :
1650 : : return k;
1651 : : }
1652 : :
1653 : : // Query for a relationship between SSA1 and SSA2, resolving unknowns
1654 : : // starting at block BB.
1655 : :
1656 : : relation_kind
1657 : 39906280 : path_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1658 : : {
1659 : 39906280 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1660 : 39906280 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1661 : :
1662 : 39906280 : if (v1 == v2)
1663 : : return VREL_EQ;
1664 : :
1665 : 39833716 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
1666 : 39833716 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
1667 : 39833716 : if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
1668 : : return VREL_EQ;
1669 : :
1670 : 39437420 : return query_relation (bb, equiv_1, equiv_2);
1671 : : }
1672 : :
1673 : : // Reset any relations registered on this path. ORACLE is the root
1674 : : // oracle to use.
1675 : :
1676 : : void
1677 : 20039060 : path_oracle::reset_path (relation_oracle *oracle)
1678 : : {
1679 : 20039060 : set_root_oracle (oracle);
1680 : 20039060 : m_equiv.m_next = NULL;
1681 : 20039060 : bitmap_clear (m_equiv.m_names);
1682 : 20039060 : m_relations.m_head = NULL;
1683 : 20039060 : bitmap_clear (m_relations.m_names);
1684 : 20039060 : bitmap_clear (m_killed_defs);
1685 : 20039060 : }
1686 : :
1687 : : // Dump relation in basic block... Do nothing here.
1688 : :
1689 : : void
1690 : 0 : path_oracle::dump (FILE *, basic_block) const
1691 : : {
1692 : 0 : }
1693 : :
1694 : : // Dump the relations and equivalencies found in the path.
1695 : :
1696 : : void
1697 : 0 : path_oracle::dump (FILE *f) const
1698 : : {
1699 : 0 : equiv_chain *ptr = m_equiv.m_next;
1700 : 0 : relation_chain *ptr2 = m_relations.m_head;
1701 : :
1702 : 0 : if (ptr || ptr2)
1703 : 0 : fprintf (f, "\npath_oracle:\n");
1704 : :
1705 : 0 : for (; ptr; ptr = ptr->m_next)
1706 : 0 : ptr->dump (f);
1707 : :
1708 : 0 : for (; ptr2; ptr2 = ptr2->m_next)
1709 : : {
1710 : 0 : fprintf (f, "Relational : ");
1711 : 0 : ptr2->dump (f);
1712 : 0 : fprintf (f, "\n");
1713 : : }
1714 : 0 : }
1715 : :
1716 : : // ------------------------------------------------------------------------
1717 : : // EQUIV iterator. Although we have bitmap iterators, don't expose that it
1718 : : // is currently a bitmap. Use an export iterator to hide future changes.
1719 : :
1720 : : // Construct a basic iterator over an equivalence bitmap.
1721 : :
1722 : 39566385 : equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle,
1723 : : basic_block bb, tree name,
1724 : 39566385 : bool full, bool partial)
1725 : : {
1726 : 39566385 : m_name = name;
1727 : 39566385 : m_oracle = oracle;
1728 : 39566385 : m_pe = partial ? oracle->partial_equiv_set (name) : NULL;
1729 : 39566385 : m_bm = NULL;
1730 : 39566385 : if (full)
1731 : 39566385 : m_bm = oracle->equiv_set (name, bb);
1732 : 39566385 : if (!m_bm && m_pe)
1733 : 0 : m_bm = m_pe->members;
1734 : 39566385 : if (m_bm)
1735 : 39566385 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
1736 : 39566385 : }
1737 : :
1738 : : // Move to the next export bitmap spot.
1739 : :
1740 : : void
1741 : 51549301 : equiv_relation_iterator::next ()
1742 : : {
1743 : 51549301 : bmp_iter_next (&m_bi, &m_y);
1744 : 51549301 : }
1745 : :
1746 : : // Fetch the name of the next export in the export list. Return NULL if
1747 : : // iteration is done.
1748 : :
1749 : : tree
1750 : 46938550 : equiv_relation_iterator::get_name (relation_kind *rel)
1751 : : {
1752 : 51549270 : if (!m_bm)
1753 : : return NULL_TREE;
1754 : :
1755 : 95726406 : while (bmp_iter_set (&m_bi, &m_y))
1756 : : {
1757 : : // Do not return self.
1758 : 51549301 : tree t = ssa_name (m_y);
1759 : 51549301 : if (t && t != m_name)
1760 : : {
1761 : 7372165 : relation_kind k = VREL_EQ;
1762 : 7372165 : if (m_pe && m_bm == m_pe->members)
1763 : : {
1764 : 5985482 : const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t);
1765 : 5985482 : if (equiv_pe && equiv_pe->members == m_pe->members)
1766 : 5985482 : k = pe_min (m_pe->code, equiv_pe->code);
1767 : : else
1768 : : k = VREL_VARYING;
1769 : : }
1770 : 5985482 : if (relation_equiv_p (k))
1771 : : {
1772 : 7372165 : if (rel)
1773 : 7372165 : *rel = k;
1774 : 7372165 : return t;
1775 : : }
1776 : : }
1777 : 44177136 : next ();
1778 : : }
1779 : :
1780 : : // Process partial equivs after full equivs if both were requested.
1781 : 44177105 : if (m_pe && m_bm != m_pe->members)
1782 : : {
1783 : 39566385 : m_bm = m_pe->members;
1784 : 39566385 : if (m_bm)
1785 : : {
1786 : : // Recursively call back to process First PE.
1787 : 4610720 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
1788 : 4610720 : return get_name (rel);
1789 : : }
1790 : : }
1791 : : return NULL_TREE;
1792 : : }
1793 : :
1794 : : #if CHECKING_P
1795 : : #include "selftest.h"
1796 : :
1797 : : namespace selftest
1798 : : {
1799 : : void
1800 : 4 : relation_tests ()
1801 : : {
1802 : : // rr_*_table tables use unsigned char rather than relation_kind.
1803 : 4 : ASSERT_LT (VREL_LAST, UCHAR_MAX);
1804 : : // Verify commutativity of relation_intersect and relation_union.
1805 : 36 : for (relation_kind r1 = VREL_VARYING; r1 < VREL_PE8;
1806 : 32 : r1 = relation_kind (r1 + 1))
1807 : 288 : for (relation_kind r2 = VREL_VARYING; r2 < VREL_PE8;
1808 : 256 : r2 = relation_kind (r2 + 1))
1809 : : {
1810 : 256 : ASSERT_EQ (relation_intersect (r1, r2), relation_intersect (r2, r1));
1811 : 256 : ASSERT_EQ (relation_union (r1, r2), relation_union (r2, r1));
1812 : : }
1813 : 4 : }
1814 : :
1815 : : } // namespace selftest
1816 : :
1817 : : #endif // CHECKING_P
|
