Line data Source code
1 : /* Header file for the value range relational processing.
2 : Copyright (C) 2020-2026 Free Software Foundation, Inc.
3 : Contributed by Andrew MacLeod <amacleod@redhat.com>
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it under
8 : the terms of the GNU General Public License as published by the Free
9 : Software Foundation; either version 3, or (at your option) any later
10 : version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "backend.h"
25 : #include "tree.h"
26 : #include "gimple.h"
27 : #include "ssa.h"
28 :
29 : #include "gimple-range.h"
30 : #include "tree-pretty-print.h"
31 : #include "gimple-pretty-print.h"
32 : #include "alloc-pool.h"
33 : #include "dominance.h"
34 :
35 : static const char *const kind_string[VREL_LAST] =
36 : { "varying", "undefined", "<", "<=", ">", ">=", "==", "!=", "pe8", "pe16",
37 : "pe32", "pe64" };
38 :
39 : // Print a relation_kind REL to file F.
40 :
41 : void
42 39328 : print_relation (FILE *f, relation_kind rel)
43 : {
44 39328 : fprintf (f, " %s ", kind_string[rel]);
45 39328 : }
46 :
47 : // This table is used to negate the operands. op1 REL op2 -> !(op1 REL op2).
48 : // Partial equivalence can't be negated, so VARYING is correct.
49 : static const unsigned char rr_negate_table[VREL_LAST] = {
50 : VREL_VARYING, VREL_UNDEFINED, VREL_GE, VREL_GT, VREL_LE, VREL_LT, VREL_NE,
51 : VREL_EQ, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING };
52 :
53 : // Negate the relation, as in logical negation.
54 :
55 : relation_kind
56 0 : relation_negate (relation_kind r)
57 : {
58 0 : return relation_kind (rr_negate_table [r]);
59 : }
60 :
61 : // This table is used to swap the operands. op1 REL op2 -> op2 REL op1.
62 : // Partial equivalences swap to themselves as the low N bits are equal.
63 : static const unsigned char rr_swap_table[VREL_LAST] = {
64 : VREL_VARYING, VREL_UNDEFINED, VREL_GT, VREL_GE, VREL_LT, VREL_LE, VREL_EQ,
65 : VREL_NE, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 };
66 :
67 : // Return the relation as if the operands were swapped.
68 :
69 : relation_kind
70 51065692 : relation_swap (relation_kind r)
71 : {
72 51065692 : return relation_kind (rr_swap_table [r]);
73 : }
74 :
75 : // This table is used to perform an intersection between 2 relations.
76 : // EQ is a full equivalency, and thus replaces any partial equivalence.
77 : // Likewise, the higher bit PE is more "equivalent" than the lower bit version
78 : // and thus more restrictive.
79 :
80 : static const unsigned char rr_intersect_table[VREL_LAST][VREL_LAST] = {
81 : // VREL_VARYING
82 : { VREL_VARYING, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ,
83 : VREL_NE, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
84 : // VREL_UNDEFINED
85 : { VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED,
86 : VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED,
87 : VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED },
88 : // VREL_LT
89 : { VREL_LT, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_UNDEFINED, VREL_UNDEFINED,
90 : VREL_UNDEFINED, VREL_LT,
91 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
92 : // VREL_LE
93 : { VREL_LE, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_UNDEFINED, VREL_EQ,
94 : VREL_EQ, VREL_LT,
95 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
96 : // VREL_GT
97 : { VREL_GT, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_GT, VREL_GT,
98 : VREL_UNDEFINED, VREL_GT,
99 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
100 : // VREL_GE
101 : { VREL_GE, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_GT, VREL_GE,
102 : VREL_EQ, VREL_GT,
103 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
104 : // VREL_EQ
105 : { VREL_EQ, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_UNDEFINED, VREL_EQ,
106 : VREL_EQ, VREL_UNDEFINED,
107 : VREL_EQ, VREL_EQ, VREL_EQ, VREL_EQ },
108 : // VREL_NE
109 : { VREL_NE, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_GT, VREL_GT,
110 : VREL_UNDEFINED, VREL_NE,
111 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
112 : // VREL_PE8
113 : { VREL_PE8, VREL_UNDEFINED, VREL_VARYING, VREL_VARYING, VREL_VARYING,
114 : VREL_VARYING, VREL_EQ, VREL_VARYING,
115 : VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
116 : // VREL_PE16
117 : { VREL_PE16, VREL_UNDEFINED, VREL_VARYING, VREL_VARYING, VREL_VARYING,
118 : VREL_VARYING, VREL_EQ, VREL_VARYING,
119 : VREL_PE16, VREL_PE16, VREL_PE32, VREL_PE64 },
120 : // VREL_PE32
121 : { VREL_PE32, VREL_UNDEFINED, VREL_VARYING, VREL_VARYING, VREL_VARYING,
122 : VREL_VARYING, VREL_EQ, VREL_VARYING,
123 : VREL_PE32, VREL_PE32, VREL_PE32, VREL_PE64 },
124 : // VREL_PE64
125 : { VREL_PE64, VREL_UNDEFINED, VREL_VARYING, VREL_VARYING, VREL_VARYING,
126 : VREL_VARYING, VREL_EQ, VREL_VARYING,
127 : VREL_PE64, VREL_PE64, VREL_PE64, VREL_PE64 } };
128 :
129 :
130 : // Intersect relation R1 with relation R2 and return the resulting relation.
131 :
132 : relation_kind
133 127796515 : relation_intersect (relation_kind r1, relation_kind r2)
134 : {
135 127796515 : return relation_kind (rr_intersect_table[r1][r2]);
136 : }
137 :
138 :
139 : // This table is used to perform a union between 2 relations.
140 : // EQ unions with a PE to produce the same PE, and likewise whichever PE
141 : // has the least common bits forms the union.
142 :
143 : static const unsigned char rr_union_table[VREL_LAST][VREL_LAST] = {
144 : // VREL_VARYING
145 : { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
146 : VREL_VARYING, VREL_VARYING, VREL_VARYING,
147 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
148 : // VREL_UNDEFINED
149 : { VREL_VARYING, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_GT, VREL_GE,
150 : VREL_EQ, VREL_NE, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
151 : // VREL_LT
152 : { VREL_VARYING, VREL_LT, VREL_LT, VREL_LE, VREL_NE, VREL_VARYING, VREL_LE,
153 : VREL_NE, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
154 : // VREL_LE
155 : { VREL_VARYING, VREL_LE, VREL_LE, VREL_LE, VREL_VARYING, VREL_VARYING,
156 : VREL_LE, VREL_VARYING,
157 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
158 : // VREL_GT
159 : { VREL_VARYING, VREL_GT, VREL_NE, VREL_VARYING, VREL_GT, VREL_GE, VREL_GE,
160 : VREL_NE, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
161 : // VREL_GE
162 : { VREL_VARYING, VREL_GE, VREL_VARYING, VREL_VARYING, VREL_GE, VREL_GE,
163 : VREL_GE, VREL_VARYING,
164 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
165 : // VREL_EQ
166 : { VREL_VARYING, VREL_EQ, VREL_LE, VREL_LE, VREL_GE, VREL_GE, VREL_EQ,
167 : VREL_VARYING, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
168 : // VREL_NE
169 : { VREL_VARYING, VREL_NE, VREL_NE, VREL_VARYING, VREL_NE, VREL_VARYING,
170 : VREL_VARYING, VREL_NE,
171 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
172 : // VREL_PE8
173 : { VREL_VARYING, VREL_PE8, VREL_VARYING, VREL_VARYING, VREL_VARYING,
174 : VREL_VARYING, VREL_PE8, VREL_VARYING,
175 : VREL_PE8, VREL_PE8, VREL_PE8, VREL_PE8 },
176 : // VREL_PE16
177 : { VREL_VARYING, VREL_PE16, VREL_VARYING, VREL_VARYING, VREL_VARYING,
178 : VREL_VARYING, VREL_PE16, VREL_VARYING,
179 : VREL_PE8, VREL_PE16, VREL_PE16, VREL_PE16 },
180 : // VREL_PE32
181 : { VREL_VARYING, VREL_PE32, VREL_VARYING, VREL_VARYING, VREL_VARYING,
182 : VREL_VARYING, VREL_PE32, VREL_VARYING,
183 : VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE32 },
184 : // VREL_PE64
185 : { VREL_VARYING, VREL_PE64, VREL_VARYING, VREL_VARYING, VREL_VARYING,
186 : VREL_VARYING, VREL_PE64, VREL_VARYING,
187 : VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 } };
188 :
189 : // Union relation R1 with relation R2 and return the result.
190 :
191 : relation_kind
192 92714210 : relation_union (relation_kind r1, relation_kind r2)
193 : {
194 92714210 : return relation_kind (rr_union_table[r1][r2]);
195 : }
196 :
197 :
198 : // This table is used to determine transitivity between 2 relations.
199 : // (A relation0 B) and (B relation1 C) implies (A result C)
200 : // Chaining two partial equivalences leaves only the bits both agree on, ie
201 : // the narrower of the two.
202 :
203 : static const unsigned char rr_transitive_table[VREL_LAST][VREL_LAST] = {
204 : // VREL_VARYING
205 : { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
206 : VREL_VARYING, VREL_VARYING, VREL_VARYING,
207 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
208 : // VREL_UNDEFINED
209 : { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
210 : VREL_VARYING, VREL_VARYING, VREL_VARYING,
211 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
212 : // VREL_LT
213 : { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LT, VREL_VARYING, VREL_VARYING,
214 : VREL_LT, VREL_VARYING,
215 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
216 : // VREL_LE
217 : { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_VARYING, VREL_VARYING,
218 : VREL_LE, VREL_VARYING,
219 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
220 : // VREL_GT
221 : { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GT,
222 : VREL_GT, VREL_VARYING,
223 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
224 : // VREL_GE
225 : { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GE,
226 : VREL_GE, VREL_VARYING,
227 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
228 : // VREL_EQ
229 : { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ,
230 : VREL_NE, VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 },
231 : // VREL_NE
232 : { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
233 : VREL_VARYING, VREL_NE, VREL_VARYING,
234 : VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING },
235 : // VREL_PE8
236 : { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
237 : VREL_VARYING, VREL_PE8, VREL_VARYING,
238 : VREL_PE8, VREL_PE8, VREL_PE8, VREL_PE8 },
239 : // VREL_PE16
240 : { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
241 : VREL_VARYING, VREL_PE16, VREL_VARYING,
242 : VREL_PE8, VREL_PE16, VREL_PE16, VREL_PE16 },
243 : // VREL_PE32
244 : { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
245 : VREL_VARYING, VREL_PE32, VREL_VARYING,
246 : VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE32 },
247 : // VREL_PE64
248 : { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING,
249 : VREL_VARYING, VREL_PE64, VREL_VARYING,
250 : VREL_PE8, VREL_PE16, VREL_PE32, VREL_PE64 } };
251 :
252 : // Apply transitive operation between relation R1 and relation R2, and
253 : // return the resulting relation, if any.
254 :
255 : relation_kind
256 53702735 : relation_transitive (relation_kind r1, relation_kind r2)
257 : {
258 53702735 : return relation_kind (rr_transitive_table[r1][r2]);
259 : }
260 :
261 : // When one name is an equivalence of another, ensure the equivalence
262 : // range is correct. Specifically for floating point, a +0 is also
263 : // equivalent to a -0 which may not be reflected. See PR 111694.
264 :
265 : void
266 2533080 : adjust_equivalence_range (vrange &range)
267 : {
268 2533080 : if (range.undefined_p () || !is_a<frange> (range))
269 2496690 : return;
270 :
271 36390 : frange fr = as_a<frange> (range);
272 : // If range includes 0 make sure both signs of zero are included.
273 36390 : if (fr.contains_p (dconst0) || fr.contains_p (dconstm0))
274 : {
275 19335 : frange zeros (range.type (), dconstm0, dconst0);
276 19335 : range.union_ (zeros);
277 19335 : }
278 36390 : }
279 :
280 : // Given an equivalence set EQUIV, set all the bits in B that are still valid
281 : // members of EQUIV in basic block BB.
282 :
283 : void
284 25043229 : relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
285 : {
286 25043229 : unsigned i;
287 25043229 : bitmap_iterator bi;
288 52792825 : EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
289 : {
290 27749596 : tree ssa = ssa_name (i);
291 55499192 : if (ssa && !SSA_NAME_IN_FREE_LIST (ssa))
292 : {
293 27749596 : const_bitmap ssa_equiv = equiv_set (ssa, bb);
294 27749596 : if (ssa_equiv == equivs)
295 27453302 : bitmap_set_bit (b, i);
296 : }
297 : }
298 25043229 : }
299 :
300 : // Return any known relation between SSA1 and SSA2 before stmt S is executed.
301 : // If GET_RANGE is true, query the range of both operands first to ensure
302 : // the definitions have been processed and any relations have be created.
303 :
304 : relation_kind
305 140210257 : relation_oracle::query (gimple *s, tree ssa1, tree ssa2)
306 : {
307 140210257 : if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
308 : return VREL_VARYING;
309 60273944 : return query (gimple_bb (s), ssa1, ssa2);
310 : }
311 :
312 : // Return any known relation between SSA1 and SSA2 on edge E.
313 : // If GET_RANGE is true, query the range of both operands first to ensure
314 : // the definitions have been processed and any relations have be created.
315 :
316 : relation_kind
317 49372810 : relation_oracle::query (edge e, tree ssa1, tree ssa2)
318 : {
319 49372810 : basic_block bb;
320 49372810 : if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
321 : return VREL_VARYING;
322 :
323 : // Use destination block if it has a single predecessor, and this picks
324 : // up any relation on the edge.
325 : // Otherwise choose the src edge and the result is the same as on-exit.
326 36301476 : if (!single_pred_p (e->dest))
327 34355106 : bb = e->src;
328 : else
329 : bb = e->dest;
330 :
331 36301476 : return query (bb, ssa1, ssa2);
332 : }
333 : // -------------------------------------------------------------------------
334 :
335 : // The very first element in the m_equiv chain is actually just a summary
336 : // element in which the m_names bitmap is used to indicate that an ssa_name
337 : // has an equivalence set in this block.
338 : // This allows for much faster traversal of the DOM chain, as a search for
339 : // SSA_NAME simply requires walking the DOM chain until a block is found
340 : // which has the bit for SSA_NAME set. Then scan for the equivalency set in
341 : // that block. No previous lists need be searched.
342 :
343 : // If SSA has an equivalence in this list, find and return it.
344 : // Otherwise return NULL.
345 :
346 : equiv_chain *
347 217222819 : equiv_chain::find (unsigned ssa)
348 : {
349 217222819 : equiv_chain *ptr = NULL;
350 : // If there are equiv sets and SSA is in one in this list, find it.
351 : // Otherwise return NULL.
352 217222819 : if (bitmap_bit_p (m_names, ssa))
353 : {
354 247204976 : for (ptr = m_next; ptr; ptr = ptr->m_next)
355 247204976 : if (bitmap_bit_p (ptr->m_names, ssa))
356 : break;
357 : }
358 217222819 : return ptr;
359 : }
360 :
361 : // Dump the names in this equivalence set.
362 :
363 : void
364 12 : equiv_chain::dump (FILE *f) const
365 : {
366 12 : bitmap_iterator bi;
367 12 : unsigned i;
368 :
369 12 : if (!m_names || bitmap_empty_p (m_names))
370 1 : return;
371 11 : fprintf (f, "Equivalence set : [");
372 11 : unsigned c = 0;
373 29 : EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
374 : {
375 18 : if (ssa_name (i))
376 : {
377 18 : if (c++)
378 7 : fprintf (f, ", ");
379 18 : print_generic_expr (f, ssa_name (i), TDF_SLIM);
380 : }
381 : }
382 11 : fprintf (f, "]\n");
383 : }
384 :
385 : // Instantiate an equivalency oracle.
386 :
387 27831547 : equiv_oracle::equiv_oracle ()
388 : {
389 27831547 : bitmap_obstack_initialize (&m_bitmaps);
390 27831547 : m_equiv.create (0);
391 27831547 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
392 27831547 : m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
393 27831547 : bitmap_tree_view (m_equiv_set);
394 27831547 : obstack_init (&m_chain_obstack);
395 27831547 : m_name_info.create (0);
396 55663094 : m_name_info.safe_grow_cleared (num_ssa_names + 1);
397 27831547 : m_partial.create (0);
398 55663094 : m_partial.safe_grow_cleared (num_ssa_names + 1);
399 : // Create a bitmap to avoid registering multiple equivalences from a LHS.
400 : // See PR 124809.
401 27831547 : m_lhs_equiv_set_p = BITMAP_ALLOC (&m_bitmaps);
402 27831547 : bitmap_tree_view (m_lhs_equiv_set_p);
403 27831547 : }
404 :
405 : // Destruct an equivalency oracle.
406 :
407 27831547 : equiv_oracle::~equiv_oracle ()
408 : {
409 27831547 : m_partial.release ();
410 27831547 : m_name_info.release ();
411 27831547 : obstack_free (&m_chain_obstack, NULL);
412 27831547 : m_equiv.release ();
413 27831547 : bitmap_obstack_release (&m_bitmaps);
414 27831547 : }
415 :
416 : // Add a partial equivalence R between OP1 and OP2. Return false if no
417 : // new relation is added.
418 :
419 : bool
420 10515992 : equiv_oracle::add_partial_equiv (relation_kind r, tree op1, tree op2)
421 : {
422 10515992 : int v1 = SSA_NAME_VERSION (op1);
423 10515992 : int v2 = SSA_NAME_VERSION (op2);
424 10515992 : int prec2 = TYPE_PRECISION (TREE_TYPE (op2));
425 10515992 : int bits = pe_to_bits (r);
426 10515992 : gcc_checking_assert (bits && prec2 >= bits);
427 :
428 21031984 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
429 9958 : m_partial.safe_grow_cleared (num_ssa_names + 1);
430 21031984 : gcc_checking_assert (v1 < (int)m_partial.length ()
431 : && v2 < (int)m_partial.length ());
432 :
433 10515992 : pe_slice &pe1 = m_partial[v1];
434 10515992 : pe_slice &pe2 = m_partial[v2];
435 :
436 10515992 : if (pe1.members)
437 : {
438 : // If the definition pe1 already has an entry, either the stmt is
439 : // being re-evaluated, or the def was used before being registered.
440 : // In either case, if PE2 has an entry, we simply do nothing.
441 209 : if (pe2.members)
442 : return false;
443 : // If there are no uses of op2, do not register.
444 185 : if (has_zero_uses (op2))
445 : return false;
446 : // PE1 is the LHS and already has members, so everything in the set
447 : // should be a slice of PE2 rather than PE1.
448 185 : pe2.code = pe_min (r, pe1.code);
449 185 : pe2.ssa_base = op2;
450 185 : pe2.members = pe1.members;
451 185 : bitmap_iterator bi;
452 185 : unsigned x;
453 563 : EXECUTE_IF_SET_IN_BITMAP (pe1.members, 0, x, bi)
454 : {
455 378 : m_partial[x].ssa_base = op2;
456 378 : m_partial[x].code = pe_min (m_partial[x].code, pe2.code);
457 : }
458 185 : bitmap_set_bit (pe1.members, v2);
459 185 : return true;
460 : }
461 10515783 : if (pe2.members)
462 : {
463 : // If there are no uses of op1, do not register.
464 778614 : if (has_zero_uses (op1))
465 : return false;
466 764180 : pe1.ssa_base = pe2.ssa_base;
467 : // If pe2 is a 16 bit value, but only an 8 bit copy, we can't be any
468 : // more than an 8 bit equivalence here, so choose MIN value.
469 764180 : pe1.code = pe_min (r, pe2.code);
470 764180 : pe1.members = pe2.members;
471 764180 : bitmap_set_bit (pe1.members, v1);
472 : }
473 : else
474 : {
475 : // If there are no uses of either operand, do not register.
476 9737169 : if (has_zero_uses (op1) || has_zero_uses (op2))
477 : return false;
478 : // Neither name has an entry, simply create op1 as slice of op2.
479 9583276 : pe2.code = bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2)));
480 9583276 : if (pe2.code == VREL_VARYING)
481 : return false;
482 9527002 : pe2.ssa_base = op2;
483 9527002 : pe2.members = BITMAP_ALLOC (&m_bitmaps);
484 9527002 : bitmap_set_bit (pe2.members, v2);
485 9527002 : pe1.ssa_base = op2;
486 9527002 : pe1.code = r;
487 9527002 : pe1.members = pe2.members;
488 9527002 : bitmap_set_bit (pe1.members, v1);
489 : }
490 : return true;
491 : }
492 :
493 : // Return the set of partial equivalences associated with NAME. The bitmap
494 : // will be NULL if there are none.
495 :
496 : const pe_slice *
497 63703836 : equiv_oracle::partial_equiv_set (tree name)
498 : {
499 63703836 : int v = SSA_NAME_VERSION (name);
500 127407672 : if (v >= (int)m_partial.length ())
501 : return NULL;
502 63703836 : return &m_partial[v];
503 : }
504 :
505 : // Query if there is a partial equivalence between SSA1 and SSA2. Return
506 : // VREL_VARYING if there is not one. If BASE is non-null, return the base
507 : // ssa-name this is a slice of.
508 :
509 : relation_kind
510 109527843 : equiv_oracle::partial_equiv (tree ssa1, tree ssa2, tree *base) const
511 : {
512 109527843 : int v1 = SSA_NAME_VERSION (ssa1);
513 109527843 : int v2 = SSA_NAME_VERSION (ssa2);
514 :
515 219055686 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
516 : return VREL_VARYING;
517 :
518 109527135 : const pe_slice &pe1 = m_partial[v1];
519 109527135 : const pe_slice &pe2 = m_partial[v2];
520 109527135 : if (pe1.members && pe2.members == pe1.members)
521 : {
522 36098 : if (base)
523 0 : *base = pe1.ssa_base;
524 36098 : return pe_min (pe1.code, pe2.code);
525 : }
526 : return VREL_VARYING;
527 : }
528 :
529 : void
530 21158181 : equiv_oracle::register_equiv_block (unsigned v, unsigned bbi)
531 : {
532 21158181 : if (v >= m_name_info.length ())
533 68 : m_name_info.safe_grow_cleared (num_ssa_names + 1);
534 :
535 21158181 : if (!m_name_info[v].m_block_list)
536 9663997 : m_name_info[v].m_block_list = BITMAP_ALLOC (&m_bitmaps);
537 :
538 21158181 : bitmap_set_bit (m_name_info[v].m_block_list, bbi);
539 21158181 : }
540 :
541 : void
542 15707868 : equiv_oracle::register_equiv_block (const_bitmap names, basic_block bb)
543 : {
544 15707868 : bitmap_iterator bi;
545 15707868 : unsigned v;
546 :
547 36834862 : EXECUTE_IF_SET_IN_BITMAP (names, 0, v, bi)
548 21126994 : register_equiv_block (v, bb->index);
549 15707868 : }
550 :
551 : // Find and return the equivalency set for SSA along the dominators of BB.
552 : // This is the external API.
553 :
554 : const_bitmap
555 179215041 : equiv_oracle::equiv_set (tree ssa, basic_block bb)
556 : {
557 : // Search the dominator tree for an equivalency.
558 179215041 : equiv_chain *equiv = find_equiv_dom (ssa, bb);
559 179215041 : if (equiv)
560 22899576 : return equiv->m_names;
561 :
562 : // Otherwise return a cached equiv set containing just this SSA.
563 156315465 : unsigned v = SSA_NAME_VERSION (ssa);
564 156315465 : if (v >= m_name_info.length ())
565 9166 : m_name_info.safe_grow_cleared (num_ssa_names + 1);
566 :
567 156315465 : if (!m_name_info[v].m_self_equiv)
568 : {
569 39305440 : m_name_info[v].m_self_equiv = BITMAP_ALLOC (&m_bitmaps);
570 39305440 : bitmap_set_bit (m_name_info[v].m_self_equiv, v);
571 : }
572 156315465 : return m_name_info[v].m_self_equiv;
573 : }
574 :
575 : // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
576 :
577 : relation_kind
578 0 : equiv_oracle::query (basic_block bb, tree ssa1, tree ssa2)
579 : {
580 : // If the 2 ssa names share the same equiv set, they are equal.
581 0 : if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb))
582 : return VREL_EQ;
583 :
584 : // Check if there is a partial equivalence.
585 0 : return partial_equiv (ssa1, ssa2);
586 : }
587 :
588 : // Query if there is a relation (equivalence) between 2 SSA_NAMEs.
589 :
590 : relation_kind
591 0 : equiv_oracle::query (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1,
592 : const_bitmap e2)
593 : {
594 : // If the 2 ssa names share the same equiv set, they are equal.
595 0 : if (bitmap_equal_p (e1, e2))
596 0 : return VREL_EQ;
597 : return VREL_VARYING;
598 : }
599 :
600 : // If SSA has an equivalence in block BB, find and return it.
601 : // Otherwise return NULL.
602 :
603 : equiv_chain *
604 164041077 : equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
605 : {
606 328082154 : if (bb >= (int)m_equiv.length () || !m_equiv[bb])
607 : return NULL;
608 :
609 72592189 : return m_equiv[bb]->find (ssa);
610 : }
611 :
612 : // Starting at block BB, walk the dominator chain looking for the nearest
613 : // equivalence set containing NAME.
614 :
615 : equiv_chain *
616 199616407 : equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
617 : {
618 199616407 : unsigned v = SSA_NAME_VERSION (name);
619 : // Short circuit looking for names which have no equivalences.
620 : // Saves time looking for something which does not exist.
621 199616407 : if (!bitmap_bit_p (m_equiv_set, v))
622 : return NULL;
623 :
624 : // NAME has at least once equivalence set, check to see if it has one along
625 : // the dominator tree.
626 166484136 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
627 : {
628 164041077 : equiv_chain *ptr = find_equiv_block (v, bb->index);
629 164041077 : if (ptr)
630 : return ptr;
631 : }
632 : return NULL;
633 : }
634 :
635 : // Register equivalence between ssa_name V and set EQUIV in block BB,
636 :
637 : bitmap
638 93411 : equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
639 : {
640 : // V will have an equivalency now.
641 93411 : bitmap_set_bit (m_equiv_set, v);
642 :
643 : // If that equiv chain is in this block, simply use it.
644 93411 : if (equiv->m_bb == bb)
645 : {
646 31187 : bitmap_set_bit (equiv->m_names, v);
647 31187 : bitmap_set_bit (m_equiv[bb->index]->m_names, v);
648 : // Add BB to V.
649 31187 : register_equiv_block (v, bb->index);
650 31187 : return NULL;
651 : }
652 :
653 : // Otherwise create an equivalence for this block which is a copy
654 : // of equiv, the add V to the set.
655 62224 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
656 62224 : valid_equivs (b, equiv->m_names, bb);
657 62224 : bitmap_set_bit (b, v);
658 : // Add BB to the all the equiv names.
659 62224 : register_equiv_block (b, bb);
660 62224 : return b;
661 : }
662 :
663 : // Register equivalence between set equiv_1 and equiv_2 in block BB.
664 : // Return NULL if either name can be merged with the other. Otherwise
665 : // return a pointer to the combined bitmap of names. This allows the
666 : // caller to do any setup required for a new element.
667 :
668 : bitmap
669 5309873 : equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
670 : equiv_chain *equiv_2)
671 : {
672 : // If equiv_1 is already in BB, use it as the combined set.
673 5309873 : if (equiv_1->m_bb == bb)
674 : {
675 3481152 : valid_equivs (equiv_1->m_names, equiv_2->m_names, bb);
676 : // Its hard to delete from a single linked list, so
677 : // just clear the second one.
678 3481152 : if (equiv_2->m_bb == bb)
679 1134439 : bitmap_clear (equiv_2->m_names);
680 : else
681 : {
682 : // Ensure the new names are in the summary for BB.
683 2346713 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
684 : // Add BB to the names in equiv2.
685 2346713 : register_equiv_block (equiv_2->m_names, bb);
686 : }
687 : return NULL;
688 : }
689 : // If equiv_2 is in BB, use it for the combined set.
690 1828721 : if (equiv_2->m_bb == bb)
691 : {
692 2397 : valid_equivs (equiv_2->m_names, equiv_1->m_names, bb);
693 : // Ensure the new names are in the summary.
694 2397 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
695 : // Add BB to the names in equiv1.
696 2397 : register_equiv_block (equiv_1->m_names, bb);
697 2397 : return NULL;
698 : }
699 :
700 : // At this point, neither equivalence is from this block.
701 1826324 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
702 1826324 : valid_equivs (b, equiv_1->m_names, bb);
703 1826324 : valid_equivs (b, equiv_2->m_names, bb);
704 : // Add BB to the all the equiv names.
705 1826324 : register_equiv_block (b, bb);
706 1826324 : return b;
707 : }
708 :
709 : // Create an equivalency set containing only SSA in its definition block.
710 : // This is done the first time SSA is registered in an equivalency and blocks
711 : // any DOM searches past the definition.
712 :
713 : void
714 9663997 : equiv_oracle::register_initial_def (tree ssa)
715 : {
716 9663997 : if (SSA_NAME_IS_DEFAULT_DEF (ssa))
717 : return;
718 9571529 : basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
719 :
720 : // If defining stmt is not in the IL, simply return.
721 9571529 : if (!bb)
722 : return;
723 9571528 : gcc_checking_assert (!find_equiv_dom (ssa, bb));
724 :
725 9571528 : unsigned v = SSA_NAME_VERSION (ssa);
726 9571528 : bitmap_set_bit (m_equiv_set, v);
727 9571528 : bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps);
728 9571528 : bitmap_set_bit (equiv_set, v);
729 9571528 : add_equiv_to_block (bb, equiv_set);
730 : }
731 :
732 : // Clear the equivalence lists and partial equivalencs for NAME.
733 :
734 : void
735 277349 : equiv_oracle::clear (tree name)
736 : {
737 277349 : unsigned v = SSA_NAME_VERSION (name);
738 : // Remove NAME from any blocks it is an equivalence in.
739 277349 : if (bitmap_bit_p (m_equiv_set, v))
740 : {
741 166 : gcc_checking_assert (m_name_info[v].m_block_list);
742 166 : bitmap_iterator bi;
743 166 : unsigned bbi;
744 :
745 434 : EXECUTE_IF_SET_IN_BITMAP (m_name_info[v].m_block_list, 0, bbi, bi)
746 : {
747 268 : if (bbi >= m_equiv.length ())
748 : break;
749 268 : if (!m_equiv[bbi])
750 0 : continue;
751 268 : equiv_chain *ptr = m_equiv[bbi]->find (v);
752 268 : if (ptr)
753 : {
754 268 : bitmap_clear_bit (ptr->m_names, v);
755 268 : bitmap_clear_bit (m_equiv[bbi]->m_names, v);
756 : }
757 : }
758 166 : bitmap_clear_bit (m_equiv_set, v);
759 166 : bitmap_clear (m_name_info[v].m_block_list);
760 : }
761 : // Eliminate any partial equivs.
762 277349 : if (v < m_partial.length ())
763 214720 : m_partial[v].members = NULL;
764 277349 : }
765 :
766 :
767 : // Register an equivalence between SSA1 and SSA2 in block BB.
768 : // The equivalence oracle maintains a vector of equivalencies indexed by basic
769 : // block. When an equivalence between SSA1 and SSA2 is registered in block BB,
770 : // a query is made as to what equivalences both names have already, and
771 : // any preexisting equivalences are merged to create a single equivalence
772 : // containing all the ssa_names in this basic block.
773 : // Return false if no new relation is added.
774 :
775 : bool
776 15930911 : equiv_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
777 : {
778 : // Process partial equivalencies.
779 15930911 : if (relation_partial_equiv_p (k))
780 10515992 : return add_partial_equiv (k, ssa1, ssa2);
781 :
782 : // Only handle equality relations.
783 5414919 : if (k != VREL_EQ)
784 : return false;
785 :
786 5414919 : unsigned v1 = SSA_NAME_VERSION (ssa1);
787 5414919 : unsigned v2 = SSA_NAME_VERSION (ssa2);
788 :
789 : // If this is the first time an ssa_name has an equivalency registered
790 : // create a self-equivalency record in the def block.
791 5414919 : if (!bitmap_bit_p (m_equiv_set, v1))
792 5232458 : register_initial_def (ssa1);
793 5414919 : if (!bitmap_bit_p (m_equiv_set, v2))
794 4431539 : register_initial_def (ssa2);
795 :
796 5414919 : equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
797 5414919 : equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
798 :
799 : // Check if they are the same set
800 5414919 : if (equiv_1 && equiv_1 == equiv_2)
801 : return false;
802 :
803 5413418 : bitmap equiv_set;
804 :
805 : // Case where we have 2 SSA_NAMEs that are not in any set.
806 5413418 : if (!equiv_1 && !equiv_2)
807 : {
808 10134 : bitmap_set_bit (m_equiv_set, v1);
809 10134 : bitmap_set_bit (m_equiv_set, v2);
810 :
811 10134 : equiv_set = BITMAP_ALLOC (&m_bitmaps);
812 10134 : bitmap_set_bit (equiv_set, v1);
813 10134 : bitmap_set_bit (equiv_set, v2);
814 : }
815 5403284 : else if (!equiv_1 && equiv_2)
816 24082 : equiv_set = register_equiv (bb, v1, equiv_2);
817 5379202 : else if (equiv_1 && !equiv_2)
818 69329 : equiv_set = register_equiv (bb, v2, equiv_1);
819 : else
820 5309873 : equiv_set = register_equiv (bb, equiv_1, equiv_2);
821 :
822 : // A non-null return is a bitmap that is to be added to the current
823 : // block as a new equivalence.
824 5413418 : if (!equiv_set)
825 : return false;
826 :
827 1898682 : add_equiv_to_block (bb, equiv_set);
828 1898682 : return true;
829 : }
830 :
831 : // Add an equivalency record in block BB containing bitmap EQUIV_SET.
832 : // Note the internal caller is responsible for allocating EQUIV_SET properly.
833 :
834 : void
835 11470210 : equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
836 : {
837 11470210 : equiv_chain *ptr;
838 :
839 : // Check if this is the first time a block has an equivalence added.
840 : // and create a header block. And set the summary for this block.
841 11470210 : limit_check (bb);
842 11470210 : if (!m_equiv[bb->index])
843 : {
844 6634325 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
845 : sizeof (equiv_chain));
846 6634325 : ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
847 6634325 : bitmap_copy (ptr->m_names, equiv_set);
848 6634325 : ptr->m_bb = bb;
849 6634325 : ptr->m_next = NULL;
850 6634325 : m_equiv[bb->index] = ptr;
851 : }
852 :
853 : // Now create the element for this equiv set and initialize it.
854 11470210 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
855 11470210 : ptr->m_names = equiv_set;
856 11470210 : ptr->m_bb = bb;
857 22940420 : gcc_checking_assert (bb->index < (int)m_equiv.length ());
858 11470210 : ptr->m_next = m_equiv[bb->index]->m_next;
859 11470210 : m_equiv[bb->index]->m_next = ptr;
860 11470210 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
861 : // Add BB to the equiv set.
862 11470210 : register_equiv_block (equiv_set, bb);
863 11470210 : }
864 :
865 : // Make sure the BB vector is big enough and grow it if needed.
866 :
867 : void
868 11470210 : equiv_oracle::limit_check (basic_block bb)
869 : {
870 11470210 : int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
871 22940420 : if (i >= (int)m_equiv.length ())
872 47 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
873 11470210 : }
874 :
875 : // Dump the equivalence sets in BB to file F.
876 :
877 : void
878 257 : equiv_oracle::dump (FILE *f, basic_block bb) const
879 : {
880 514 : if (bb->index >= (int)m_equiv.length ())
881 : return;
882 : // Process equivalences.
883 257 : if (m_equiv[bb->index])
884 : {
885 10 : equiv_chain *ptr = m_equiv[bb->index]->m_next;
886 22 : for (; ptr; ptr = ptr->m_next)
887 12 : ptr->dump (f);
888 : }
889 : // Look for partial equivalences defined in this block..
890 12764 : for (unsigned i = 0; i < num_ssa_names; i++)
891 : {
892 12507 : tree name = ssa_name (i);
893 17757 : if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name))
894 7257 : continue;
895 5250 : if (i >= m_partial.length ())
896 : break;
897 5250 : tree base = m_partial[i].ssa_base;
898 5250 : if (base && name != base && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb)
899 : {
900 42 : relation_kind k = partial_equiv (name, base);
901 42 : if (k != VREL_VARYING)
902 : {
903 42 : value_relation vr (k, name, base);
904 42 : fprintf (f, "Partial equiv ");
905 42 : vr.dump (f);
906 42 : fputc ('\n',f);
907 : }
908 : }
909 : }
910 : }
911 :
912 : // Dump all equivalence sets known to the oracle.
913 :
914 : void
915 0 : equiv_oracle::dump (FILE *f) const
916 : {
917 0 : fprintf (f, "Equivalency dump\n");
918 0 : for (unsigned i = 0; i < m_equiv.length (); i++)
919 0 : if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
920 : {
921 0 : fprintf (f, "BB%d\n", i);
922 0 : dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
923 : }
924 0 : }
925 :
926 :
927 : // --------------------------------------------------------------------------
928 :
929 : // Adjust the relation by Swapping the operands and relation.
930 :
931 : void
932 0 : value_relation::swap ()
933 : {
934 0 : related = relation_swap (related);
935 0 : tree tmp = name1;
936 0 : name1 = name2;
937 0 : name2 = tmp;
938 0 : }
939 :
940 : // Perform an intersection between 2 relations. *this &&= p.
941 : // Return false if the relations cannot be intersected.
942 :
943 : bool
944 12076909 : value_relation::intersect (value_relation &p)
945 : {
946 : // Save previous value
947 12076909 : relation_kind old = related;
948 :
949 12076909 : if (p.op1 () == op1 () && p.op2 () == op2 ())
950 11990832 : related = relation_intersect (kind (), p.kind ());
951 86077 : else if (p.op2 () == op1 () && p.op1 () == op2 ())
952 86077 : related = relation_intersect (kind (), relation_swap (p.kind ()));
953 : else
954 : return false;
955 :
956 12076909 : return old != related;
957 : }
958 :
959 : // Perform a union between 2 relations. *this ||= p.
960 :
961 : bool
962 0 : value_relation::union_ (value_relation &p)
963 : {
964 : // Save previous value
965 0 : relation_kind old = related;
966 :
967 0 : if (p.op1 () == op1 () && p.op2 () == op2 ())
968 0 : related = relation_union (kind(), p.kind());
969 0 : else if (p.op2 () == op1 () && p.op1 () == op2 ())
970 0 : related = relation_union (kind(), relation_swap (p.kind ()));
971 : else
972 : return false;
973 :
974 0 : return old != related;
975 : }
976 :
977 : // Identify and apply any transitive relations between REL
978 : // and THIS. Return true if there was a transformation.
979 :
980 : bool
981 54882340 : value_relation::apply_transitive (const value_relation &rel)
982 : {
983 54882340 : relation_kind k = VREL_VARYING;
984 :
985 : // Identify any common operand, and normalize the relations to
986 : // the form : A < B B < C produces A < C
987 54882340 : if (rel.op1 () == name2)
988 : {
989 : // A < B B < C
990 54882340 : if (rel.op2 () == name1)
991 : return false;
992 41600146 : k = relation_transitive (kind (), rel.kind ());
993 41600146 : if (k != VREL_VARYING)
994 : {
995 28988843 : related = k;
996 28988843 : name2 = rel.op2 ();
997 28988843 : return true;
998 : }
999 : }
1000 0 : else if (rel.op1 () == name1)
1001 : {
1002 : // B > A B < C
1003 0 : if (rel.op2 () == name2)
1004 : return false;
1005 0 : k = relation_transitive (relation_swap (kind ()), rel.kind ());
1006 0 : if (k != VREL_VARYING)
1007 : {
1008 0 : related = k;
1009 0 : name1 = name2;
1010 0 : name2 = rel.op2 ();
1011 0 : return true;
1012 : }
1013 : }
1014 0 : else if (rel.op2 () == name2)
1015 : {
1016 : // A < B C > B
1017 0 : if (rel.op1 () == name1)
1018 : return false;
1019 0 : k = relation_transitive (kind (), relation_swap (rel.kind ()));
1020 0 : if (k != VREL_VARYING)
1021 : {
1022 0 : related = k;
1023 0 : name2 = rel.op1 ();
1024 0 : return true;
1025 : }
1026 : }
1027 0 : else if (rel.op2 () == name1)
1028 : {
1029 : // B > A C > B
1030 0 : if (rel.op1 () == name2)
1031 : return false;
1032 0 : k = relation_transitive (relation_swap (kind ()),
1033 : relation_swap (rel.kind ()));
1034 0 : if (k != VREL_VARYING)
1035 : {
1036 0 : related = k;
1037 0 : name1 = name2;
1038 0 : name2 = rel.op1 ();
1039 0 : return true;
1040 : }
1041 : }
1042 : return false;
1043 : }
1044 :
1045 : // Create a trio from this value relation given LHS, OP1 and OP2.
1046 :
1047 : relation_trio
1048 68500953 : value_relation::create_trio (tree lhs, tree op1, tree op2)
1049 : {
1050 68500953 : relation_kind lhs_1;
1051 68500953 : if (lhs == name1 && op1 == name2)
1052 87139 : lhs_1 = related;
1053 68413814 : else if (lhs == name2 && op1 == name1)
1054 288968 : lhs_1 = relation_swap (related);
1055 : else
1056 : lhs_1 = VREL_VARYING;
1057 :
1058 68500953 : relation_kind lhs_2;
1059 68500953 : if (lhs == name1 && op2 == name2)
1060 113991 : lhs_2 = related;
1061 68386962 : else if (lhs == name2 && op2 == name1)
1062 418709 : lhs_2 = relation_swap (related);
1063 : else
1064 : lhs_2 = VREL_VARYING;
1065 :
1066 68500953 : relation_kind op_op;
1067 68500953 : if (op1 == name1 && op2 == name2)
1068 46841970 : op_op = related;
1069 21658983 : else if (op1 == name2 && op2 == name1)
1070 0 : op_op = relation_swap (related);
1071 21658983 : else if (op1 == op2)
1072 : op_op = VREL_EQ;
1073 : else
1074 21641509 : op_op = VREL_VARYING;
1075 :
1076 68500953 : return relation_trio (lhs_1, lhs_2, op_op);
1077 : }
1078 :
1079 : // Dump the relation to file F.
1080 :
1081 : void
1082 39168 : value_relation::dump (FILE *f) const
1083 : {
1084 39168 : if (!name1 || !name2)
1085 : {
1086 0 : fprintf (f, "no relation registered");
1087 0 : return;
1088 : }
1089 39168 : fputc ('(', f);
1090 39168 : print_generic_expr (f, op1 (), TDF_SLIM);
1091 39168 : print_relation (f, kind ());
1092 39168 : print_generic_expr (f, op2 (), TDF_SLIM);
1093 39168 : fputc(')', f);
1094 : }
1095 :
1096 : // This container is used to link relations in a chain.
1097 :
1098 : class relation_chain : public value_relation
1099 : {
1100 : public:
1101 : relation_chain *m_next;
1102 : };
1103 :
1104 : // Given relation record PTR in block BB, return the next relation in the
1105 : // list. If PTR is NULL, retrieve the first relation in BB.
1106 : // If NAME is sprecified, return only relations which include NAME.
1107 : // Return NULL when there are no relations left.
1108 :
1109 : relation_chain *
1110 90 : dom_oracle::next_relation (basic_block bb, relation_chain *ptr,
1111 : tree name) const
1112 : {
1113 90 : relation_chain *p;
1114 : // No value_relation pointer is used to initialize the iterator.
1115 90 : if (!ptr)
1116 : {
1117 39 : int bbi = bb->index;
1118 78 : if (bbi >= (int)m_relations.length())
1119 : return NULL;
1120 : else
1121 39 : p = m_relations[bbi].m_head;
1122 : }
1123 : else
1124 51 : p = ptr->m_next;
1125 :
1126 90 : if (name)
1127 0 : for ( ; p; p = p->m_next)
1128 0 : if (p->op1 () == name || p->op2 () == name)
1129 : break;
1130 : return p;
1131 : }
1132 :
1133 : // Instantiate a block relation iterator to iterate over the relations
1134 : // on exit from block BB in ORACLE. Limit this to relations involving NAME
1135 : // if specified. Return the first such relation in VR if there is one.
1136 :
1137 39 : block_relation_iterator::block_relation_iterator (const relation_oracle *oracle,
1138 : basic_block bb,
1139 : value_relation &vr,
1140 : tree name)
1141 : {
1142 39 : m_oracle = oracle;
1143 39 : m_bb = bb;
1144 39 : m_name = name;
1145 39 : m_ptr = oracle->next_relation (bb, NULL, m_name);
1146 39 : if (m_ptr)
1147 : {
1148 39 : m_done = false;
1149 39 : vr = *m_ptr;
1150 : }
1151 : else
1152 0 : m_done = true;
1153 39 : }
1154 :
1155 : // Retrieve the next relation from the iterator and return it in VR.
1156 :
1157 : void
1158 51 : block_relation_iterator::get_next_relation (value_relation &vr)
1159 : {
1160 51 : m_ptr = m_oracle->next_relation (m_bb, m_ptr, m_name);
1161 51 : if (m_ptr)
1162 : {
1163 12 : vr = *m_ptr;
1164 12 : if (m_name)
1165 : {
1166 0 : if (vr.op1 () != m_name)
1167 : {
1168 0 : gcc_checking_assert (vr.op2 () == m_name);
1169 0 : vr.swap ();
1170 : }
1171 : }
1172 : }
1173 : else
1174 39 : m_done = true;
1175 51 : }
1176 :
1177 : // ------------------------------------------------------------------------
1178 :
1179 : // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
1180 : // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1181 :
1182 : relation_kind
1183 87488238 : relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
1184 : {
1185 87488238 : if (!m_names)
1186 : return VREL_VARYING;
1187 :
1188 : // If both b1 and b2 aren't referenced in this block, cant be a relation
1189 61955568 : if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
1190 : return VREL_VARYING;
1191 :
1192 : // Search for the first relation that contains BOTH an element from B1
1193 : // and B2, and return that relation.
1194 7832470 : for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
1195 : {
1196 6825900 : unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1197 6825900 : unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1198 6825900 : if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
1199 3003579 : return ptr->kind ();
1200 3822321 : if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
1201 156847 : return relation_swap (ptr->kind ());
1202 : }
1203 :
1204 : return VREL_VARYING;
1205 : }
1206 :
1207 : // ------------------------------------------------------------------------
1208 : // frontier_data methods - what one side of a bidirectional search knows.
1209 :
1210 : // Construct frontier data allocating the bitmap from OBSTACK and side flag RHS.
1211 :
1212 55663094 : frontier_data::frontier_data (bitmap_obstack *obstack, bool rhs)
1213 : {
1214 55663094 : m_known.create (0);
1215 55663094 : m_visited = BITMAP_ALLOC (obstack);
1216 55663094 : m_root = NULL_TREE;
1217 55663094 : m_rhs = rhs;
1218 55663094 : }
1219 :
1220 : // Record that the root of this search is related to ssa version V by REL.
1221 :
1222 : void
1223 73953378 : frontier_data::set_known (unsigned v, relation_kind rel)
1224 : {
1225 73953378 : if (m_known.length () <= v)
1226 8389714 : m_known.safe_grow_cleared (num_ssa_names + 1);
1227 73953378 : m_known[v] = rel;
1228 73953378 : }
1229 :
1230 : // Return what the root of this search is known to be relative to ssa version V.
1231 :
1232 : relation_kind
1233 33590597 : frontier_data::known_relation (unsigned v) const
1234 : {
1235 33590597 : if (v < m_known.length ())
1236 33590597 : return m_known[v];
1237 : return VREL_VARYING;
1238 : }
1239 :
1240 : // Reset for the next search. Only the entries which were actually set need
1241 : // to be put back, and m_visited lists exactly those.
1242 :
1243 : void
1244 54646690 : frontier_data::clear_search ()
1245 : {
1246 54646690 : unsigned i;
1247 54646690 : bitmap_iterator bi;
1248 128567631 : EXECUTE_IF_SET_IN_BITMAP (m_visited, 0, i, bi)
1249 : {
1250 147841882 : if (i < m_known.length ())
1251 73920941 : m_known[i] = VREL_VARYING;
1252 : }
1253 54646690 : bitmap_clear (m_visited);
1254 54646690 : m_root = NULL_TREE;
1255 54646690 : }
1256 :
1257 : // ------------------------------------------------------------------------
1258 : // Instantiate a relation oracle.
1259 :
1260 55663094 : dom_oracle::dom_oracle () : m_lhs_search (&m_bitmaps, false),
1261 27831547 : m_rhs_search (&m_bitmaps, true)
1262 : {
1263 27831547 : m_relations.create (0);
1264 27831547 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1265 27831547 : m_relation_set = BITMAP_ALLOC (&m_bitmaps);
1266 27831547 : m_block_list.create (0);
1267 55663094 : m_block_list.safe_grow_cleared (num_ssa_names + 1);
1268 27831547 : m_tmp = BITMAP_ALLOC (&m_bitmaps);
1269 27831547 : m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
1270 27831547 : m_near.create (0);
1271 27831547 : m_worklist.create (0);
1272 27831547 : m_wl_ix = 0;
1273 27831547 : }
1274 :
1275 : // Destruct a relation oracle.
1276 :
1277 55663094 : dom_oracle::~dom_oracle ()
1278 : {
1279 27831547 : m_worklist.release ();
1280 27831547 : m_near.release ();
1281 27831547 : m_block_list.release ();
1282 27831547 : m_relations.release ();
1283 55663094 : }
1284 :
1285 : // Remove any relations with NAME from this list.
1286 :
1287 : void
1288 645 : relation_chain_head::clear (tree name)
1289 : {
1290 645 : unsigned v = SSA_NAME_VERSION (name);
1291 645 : if (!m_names || !bitmap_bit_p (m_names, v))
1292 : return;
1293 :
1294 645 : relation_chain *ptr, *last = NULL;;
1295 :
1296 1321 : for (ptr = m_head; ptr; ptr = ptr->m_next)
1297 : {
1298 676 : tree op1 = ptr->op1 ();
1299 676 : tree op2 = ptr->op2 ();
1300 : // Delink any elements with NAME.
1301 676 : if (op1 == name || op2 == name)
1302 : {
1303 600 : if (!last)
1304 533 : m_head = ptr->m_next;
1305 : else
1306 67 : last->m_next = ptr->m_next;
1307 600 : m_num_relations--;
1308 : }
1309 : else
1310 : last = ptr;
1311 : }
1312 : // And remove name from the possible relations in this block bitfield.
1313 645 : bitmap_clear_bit (m_names, v);
1314 : }
1315 :
1316 : // Remove any relations involving NAME from the DOM oracle
1317 :
1318 : void
1319 277349 : dom_oracle::clear (tree name)
1320 : {
1321 277349 : equiv_oracle::clear (name);
1322 277349 : unsigned v = SSA_NAME_VERSION (name);
1323 277349 : if (bitmap_bit_p (m_relation_set, v))
1324 : {
1325 439 : gcc_checking_assert (m_block_list[v]);
1326 439 : bitmap_iterator bi;
1327 439 : unsigned bbi;
1328 :
1329 1084 : EXECUTE_IF_SET_IN_BITMAP (m_block_list[v], 0, bbi, bi)
1330 : {
1331 645 : if (bbi >= m_relations.length())
1332 : break;
1333 645 : m_relations[bbi].clear (name);
1334 : }
1335 439 : bitmap_clear_bit (m_relation_set, v);
1336 439 : bitmap_clear (m_block_list[v]);
1337 : }
1338 277349 : }
1339 :
1340 : // Register relation K between ssa_name OP1 and OP2 on STMT.
1341 : // Return false if no new relation is added.
1342 :
1343 : bool
1344 34426173 : relation_oracle::record (gimple *stmt, relation_kind k, tree op1, tree op2)
1345 : {
1346 34426173 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1347 34426173 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1348 34426173 : gcc_checking_assert (stmt && gimple_bb (stmt));
1349 :
1350 : // Don't register lack of a relation.
1351 34426173 : if (k == VREL_VARYING)
1352 : return false;
1353 :
1354 : // If an equivalence is being added between a PHI and one of its arguments
1355 : // make sure that that argument is not defined in the same block.
1356 : // This can happen along back edges and the equivalence will not be
1357 : // applicable as it would require a use before def.
1358 34426173 : if (k == VREL_EQ && is_a<gphi *> (stmt))
1359 : {
1360 2172347 : tree phi_def = gimple_phi_result (stmt);
1361 2172347 : gcc_checking_assert (phi_def == op1 || phi_def == op2);
1362 2172347 : tree arg = op2;
1363 2172347 : if (phi_def == op2)
1364 0 : arg = op1;
1365 2172347 : if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
1366 : return false;
1367 : }
1368 :
1369 : // If the LHS of a statement has already been processed and an equivalence
1370 : // registered, do not register another one. See PR 124809.
1371 82878002 : if (m_lhs_equiv_set_p && relation_equiv_p (k)
1372 49085984 : && gimple_get_lhs (stmt) == op1)
1373 : {
1374 14659811 : if (!bitmap_set_bit (m_lhs_equiv_set_p, SSA_NAME_VERSION (op1)))
1375 : return false;
1376 : }
1377 33792018 : bool ret = record (gimple_bb (stmt), k, op1, op2);
1378 :
1379 33792018 : if (ret && dump_file && (dump_flags & TDF_DETAILS))
1380 : {
1381 38649 : value_relation vr (k, op1, op2);
1382 38649 : fprintf (dump_file, " Registering value_relation ");
1383 38649 : vr.dump (dump_file);
1384 38649 : fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
1385 38649 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1386 : }
1387 : return ret;
1388 : }
1389 :
1390 : // Register relation K between ssa_name OP1 and OP2 on edge E.
1391 : // Return false if no new relation is added.
1392 :
1393 : bool
1394 6941650 : relation_oracle::record (edge e, relation_kind k, tree op1, tree op2)
1395 : {
1396 6941650 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1397 6941650 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1398 :
1399 : // Do not register lack of relation, or blocks which have more than
1400 : // edge E for a predecessor.
1401 6941650 : if (k == VREL_VARYING || !single_pred_p (e->dest))
1402 : return false;
1403 :
1404 6941650 : bool ret = record (e->dest, k, op1, op2);
1405 :
1406 6941650 : if (ret && dump_file && (dump_flags & TDF_DETAILS))
1407 : {
1408 122 : value_relation vr (k, op1, op2);
1409 122 : fprintf (dump_file, " Registering value_relation ");
1410 122 : vr.dump (dump_file);
1411 122 : fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
1412 : }
1413 : return ret;
1414 : }
1415 :
1416 : // Register relation K between OP! and OP2 in block BB.
1417 : // This creates the record and searches for existing records in the dominator
1418 : // tree to merge with. Return false if no new relation is added.
1419 :
1420 : bool
1421 39679600 : dom_oracle::record (basic_block bb, relation_kind k, tree op1, tree op2)
1422 : {
1423 : // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1424 : // and no other relation makes sense.
1425 39679600 : if (op1 == op2)
1426 : return false;
1427 :
1428 : // Do not register an impossible relation.
1429 39668738 : if (k == VREL_UNDEFINED)
1430 : return false;
1431 :
1432 : // Equivalencies are handled by the equivalence oracle.
1433 39668738 : if (relation_equiv_p (k))
1434 15930911 : return equiv_oracle::record (bb, k, op1, op2);
1435 : else
1436 : {
1437 23737827 : relation_chain *ptr = search_and_merge_relation (bb, k, op1, op2);
1438 23737827 : return ptr != NULL;
1439 : }
1440 : }
1441 :
1442 : void
1443 45876826 : dom_oracle::record_relation_block (unsigned v, unsigned bbi)
1444 : {
1445 45876826 : if (v>= m_block_list.length ())
1446 10202 : m_block_list.safe_grow_cleared (num_ssa_names + 1);
1447 :
1448 45876826 : if (!m_block_list[v])
1449 32051404 : m_block_list[v] = BITMAP_ALLOC (&m_bitmaps);
1450 :
1451 45876826 : bitmap_set_bit (m_block_list[v], bbi);
1452 45876826 : }
1453 :
1454 : // Register relation K between OP1 and OP2 in block BB by creating a new
1455 : // record. It is an error for there to be an existing record.
1456 : // Return the record, or NULL if no record was created.
1457 :
1458 : relation_chain *
1459 22981452 : dom_oracle::create_relation_in_bb (basic_block bb, relation_kind k, tree op1,
1460 : tree op2)
1461 : {
1462 22981452 : int bbi = bb->index;
1463 :
1464 45962904 : if (bbi >= (int)m_relations.length())
1465 126 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1466 :
1467 22981452 : if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
1468 : return NULL;
1469 22938413 : m_relations[bbi].m_num_relations++;
1470 : // Check for an existing relation further up the DOM chain.
1471 : // By including dominating relations, The first one found in any search
1472 : // will be the aggregate of all the previous ones.
1473 :
1474 22938413 : relation_chain *ptr;
1475 :
1476 : // Summary bitmap indicating what ssa_names have relations in this BB.
1477 22938413 : bitmap bm = m_relations[bbi].m_names;
1478 22938413 : if (!bm)
1479 16459162 : bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
1480 22938413 : unsigned v1 = SSA_NAME_VERSION (op1);
1481 22938413 : unsigned v2 = SSA_NAME_VERSION (op2);
1482 :
1483 : // Assert there is no existing relation.
1484 22938413 : gcc_checking_assert (find_relation_block (bbi, op1, op2, NULL)
1485 : == VREL_VARYING);
1486 :
1487 22938413 : bitmap_set_bit (bm, v1);
1488 22938413 : bitmap_set_bit (bm, v2);
1489 22938413 : bitmap_set_bit (m_relation_set, v1);
1490 22938413 : bitmap_set_bit (m_relation_set, v2);
1491 22938413 : record_relation_block (v1, bbi);
1492 22938413 : record_relation_block (v2, bbi);
1493 :
1494 22938413 : ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1495 : sizeof (relation_chain));
1496 22938413 : ptr->set_relation (k, op1, op2);
1497 22938413 : ptr->m_next = m_relations[bbi].m_head;
1498 22938413 : m_relations[bbi].m_head = ptr;
1499 22938413 : return ptr;
1500 : }
1501 :
1502 : // Register relation K between OP1 and OP2 in block BB by searching the
1503 : // dominator tree for any existing record to merge with. If there were
1504 : // none, create a new record.
1505 : // Return the record, or NULL if no record was found or created.
1506 :
1507 : relation_chain *
1508 35058363 : dom_oracle::search_and_merge_relation (basic_block bb, relation_kind k,
1509 : tree op1, tree op2)
1510 : {
1511 : // Check for invalid relations to register.
1512 35058363 : gcc_checking_assert (k != VREL_VARYING && k != VREL_UNDEFINED
1513 : && k != VREL_EQ);
1514 :
1515 35058363 : relation_chain *ptr;
1516 35058363 : relation_kind curr = find_relation_block (bb->index, op1, op2, &ptr);
1517 :
1518 : // If there is an existing relation in this block, just intersect with it.
1519 35058363 : if (curr != VREL_VARYING)
1520 : {
1521 : // If K contradicts what is already recorded, the block is unreachable.
1522 : // Leave the existing relation alone rather than replacing it with
1523 : // UNDEFINED, matching what the dominator merge below does.
1524 12076911 : if (relation_intersect (curr, k) == VREL_UNDEFINED)
1525 : return NULL;
1526 : // If there was no change, return no record.
1527 12076909 : value_relation vr (k, op1, op2);
1528 12076909 : if (!ptr->intersect (vr))
1529 : return NULL;
1530 213878 : return ptr;
1531 : }
1532 :
1533 : // Create the relation in this block.
1534 22981452 : ptr = create_relation_in_bb (bb, k, op1, op2);
1535 22981452 : if (ptr)
1536 : {
1537 : // Check for an existing relation further up the DOM chain.
1538 : // By including dominating relations, The first one found in any search
1539 : // will be the aggregate of all the previous ones.
1540 22938413 : curr = find_relation_dom (get_immediate_dominator (CDI_DOMINATORS, bb),
1541 : op1, op2);
1542 22938413 : if (curr != VREL_VARYING)
1543 : {
1544 2791499 : curr = relation_intersect (curr, k);
1545 : // Intersect the new relation with the existing one, unless the
1546 : // result is UNDEFINED. Then just leave it.
1547 2791499 : if (curr != k && curr != VREL_UNDEFINED)
1548 149004 : ptr->set_relation (curr, op1, op2);
1549 : }
1550 : }
1551 22981452 : return ptr;
1552 : }
1553 :
1554 : // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1555 : // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1556 :
1557 : relation_kind
1558 34292284 : dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
1559 : const_bitmap b2) const
1560 : {
1561 34292284 : if (bb >= m_relations.length())
1562 : return VREL_VARYING;
1563 :
1564 34292284 : return m_relations[bb].find_relation (b1, b2);
1565 : }
1566 :
1567 : // Search the DOM tree for a relation between an element of equivalency set B1
1568 : // and B2, starting with block BB.
1569 :
1570 : relation_kind
1571 11958365 : dom_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
1572 : {
1573 11958365 : relation_kind r;
1574 11958365 : if (bitmap_equal_p (b1, b2))
1575 : return VREL_EQ;
1576 :
1577 : // If either name does not occur in a relation anywhere, there isn't one.
1578 11958365 : if (!bitmap_intersect_p (m_relation_set, b1)
1579 11958365 : || !bitmap_intersect_p (m_relation_set, b2))
1580 : return VREL_VARYING;
1581 :
1582 : // Search each block in the DOM tree checking.
1583 36070650 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1584 : {
1585 34292284 : r = find_relation_block (bb->index, b1, b2);
1586 34292284 : if (r != VREL_VARYING)
1587 : return r;
1588 : }
1589 : return VREL_VARYING;
1590 :
1591 : }
1592 :
1593 : // Find a relation in block BB between ssa version V1 and V2. If a relation
1594 : // is found, return a pointer to the chain object in OBJ.
1595 :
1596 : relation_kind
1597 669804617 : dom_oracle::find_relation_block (int bb, tree ssa1, tree ssa2,
1598 : relation_chain **obj) const
1599 : {
1600 1339609234 : if (bb >= (int)m_relations.length())
1601 : return VREL_VARYING;
1602 :
1603 669792831 : const_bitmap bm = m_relations[bb].m_names;
1604 669792831 : if (!bm)
1605 : return VREL_VARYING;
1606 :
1607 270088552 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1608 270088552 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1609 :
1610 : // If both b1 and b2 aren't referenced in this block, cant be a relation
1611 270088552 : if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1612 : return VREL_VARYING;
1613 :
1614 15152673 : relation_chain *ptr;
1615 23946141 : for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1616 : {
1617 23661878 : tree op1 = ptr->op1 ();
1618 23661878 : tree op2 = ptr->op2 ();
1619 23661878 : if (ssa1 == op1 && ssa2 == op2)
1620 : {
1621 14694132 : if (obj)
1622 11990834 : *obj = ptr;
1623 14694132 : return ptr->kind ();
1624 : }
1625 8967746 : if (ssa1 == op2 && ssa2 == op1)
1626 : {
1627 174278 : if (obj)
1628 86077 : *obj = ptr;
1629 174278 : return relation_swap (ptr->kind ());
1630 : }
1631 : }
1632 :
1633 : return VREL_VARYING;
1634 : }
1635 :
1636 : // See if a relation can be found between SSA1 and SSA2 in basic block BB based
1637 : // on values as they exist in basic block ORIG. This will only occur
1638 : // if SSA1 and SSA2 occur in the same statement together.
1639 :
1640 : relation_kind
1641 27323345 : dom_oracle::recomputed_relation (basic_block orig_bb, tree ssa1,
1642 : tree ssa2) const
1643 : {
1644 27323345 : if (ssa1 == ssa2)
1645 : return VREL_EQ;
1646 27323345 : if (!orig_bb)
1647 : return VREL_VARYING;
1648 54646690 : gori_map *gori_ssa = get_range_query (cfun)->gori_ssa ();
1649 27323345 : if (!gori_ssa)
1650 : return VREL_VARYING;
1651 39795890 : gimple_outgoing_range &gori = get_range_query (cfun)->gori ();
1652 :
1653 : // Both ssa1 and ssa2 must be exported somewhere.
1654 19897945 : if (!gori_ssa->is_export_p (ssa1) || !gori_ssa->is_export_p (ssa2))
1655 : return VREL_VARYING;
1656 :
1657 13254317 : relation_kind result = VREL_VARYING;
1658 13254317 : use_operand_p use_p;
1659 13254317 : imm_use_iterator iter;
1660 :
1661 : // Any statement with both SSA1 and SSA2 as operands may imply a relation
1662 : // between them, once the range of its LHS at ORIG_BB is known.
1663 99991045 : FOR_EACH_IMM_USE_FAST (use_p, iter, ssa1)
1664 : {
1665 86736728 : bool reversed = false;
1666 86736728 : gimple *s = USE_STMT (use_p);
1667 :
1668 : // S must be a binary assignment LHS = op1 op2
1669 86736728 : if (!is_gimple_assign (s) || gimple_num_ops (s) != 3)
1670 86554972 : continue;
1671 :
1672 : // S must strictly dominate ORIG_BB. DOMINATED_BY_P is block granular,
1673 : // so the same-block case must be excluded.
1674 11391420 : basic_block sbb = gimple_bb (s);
1675 20462368 : if (!sbb || sbb == orig_bb
1676 11391420 : || !dominated_by_p (CDI_DOMINATORS, orig_bb, sbb))
1677 9070948 : continue;
1678 :
1679 2320472 : gimple_range_op_handler s_handler (s);
1680 2320472 : if (!s_handler)
1681 71 : continue;
1682 :
1683 2320401 : if (s_handler.operand1 () == ssa1)
1684 : {
1685 : // op1 == ssa1, move on if op2 != ssa2.
1686 1766596 : if (s_handler.operand2 () != ssa2)
1687 1579480 : continue;
1688 : }
1689 : // Otherwise only move on if op1 == ssa2 && op2 == ssa1.
1690 553805 : else if (s_handler.operand1 () != ssa2 || s_handler.operand2 () != ssa1)
1691 495793 : continue;
1692 : else
1693 : reversed = true;
1694 :
1695 :
1696 : // Find the outgoing edge of SBB which must have been taken to reach
1697 : // ORIG_BB. SINGLE_PRED_P is required as well as dominance: if E->dest
1698 : // has another predecessor, it can dominate ORIG_BB via a path which
1699 : // never traversed E, and E's range would not apply.
1700 :
1701 245128 : edge e = NULL, se;
1702 245128 : edge_iterator ei;
1703 401016 : FOR_EACH_EDGE (se, ei, sbb->succs)
1704 522580 : if (single_pred_p (se->dest)
1705 366692 : && dominated_by_p (CDI_DOMINATORS, orig_bb, se->dest))
1706 : {
1707 : e = se;
1708 : break;
1709 : }
1710 245128 : if (!e)
1711 34324 : continue;
1712 :
1713 210804 : int_range_max edge_range;
1714 210804 : gimple *stmt = gori.edge_range_p (edge_range, e);
1715 210804 : if (!stmt)
1716 1583 : continue;
1717 :
1718 : // Walk back from the terminator of SBB towards S, recalculating each
1719 : // value as it would be in ORIG_BB rather than as it is on E. This is
1720 : // the whole point: RANGE_ON_ENTRY cannot supply S's LHS at ORIG_BB
1721 : // because it evaluates each dominating edge using the values available
1722 : // at that edge's source.
1723 209221 : tree lhs_s = s_handler.lhs ();
1724 209221 : value_range lhs_range (edge_range);
1725 :
1726 760254 : while (stmt && stmt != s)
1727 : {
1728 369277 : bool ret;
1729 369277 : gimple_range_op_handler handler (stmt);
1730 369277 : if (!handler)
1731 : break;
1732 :
1733 369005 : tree op1 = handler.operand1 ();
1734 369005 : tree op2 = handler.operand2 ();
1735 369005 : value_range op1_range (TREE_TYPE (op1));
1736 369005 : value_range op2_range;
1737 :
1738 : // Follow the operand whose dependency chain reaches S's LHS.
1739 369005 : bool op1_dep = gimple_range_ssa_p (op1)
1740 369005 : && (op1 == lhs_s || gori_ssa->in_chain_p (lhs_s, op1));
1741 369005 : bool op2_dep = gimple_range_ssa_p (op2)
1742 369005 : && (op2 == lhs_s || gori_ssa->in_chain_p (lhs_s, op2));
1743 369005 : if (op1_dep == op2_dep)
1744 : break;
1745 :
1746 345807 : if (op1_dep)
1747 : {
1748 235471 : if (!op2)
1749 27499 : ret = handler.calc_op1 (op1_range, lhs_range);
1750 : else
1751 : {
1752 207972 : op2_range.set_range_class (TREE_TYPE (op2));
1753 415944 : get_range_query (cfun)->range_on_entry (op2_range, orig_bb,
1754 : op2);
1755 207972 : ret = handler.calc_op1 (op1_range, lhs_range, op2_range);
1756 : }
1757 235471 : if (!ret)
1758 : break;
1759 231728 : lhs_range = op1_range;
1760 231728 : stmt = SSA_NAME_DEF_STMT (op1);
1761 : }
1762 : else
1763 : {
1764 110336 : op2_range.set_range_class (TREE_TYPE (op2));
1765 220672 : get_range_query (cfun)->range_on_entry (op1_range, orig_bb, op1);
1766 110336 : ret = handler.calc_op2 (op2_range, lhs_range, op1_range);
1767 110336 : if (!ret)
1768 : break;
1769 110084 : lhs_range = op2_range;
1770 110084 : stmt = SSA_NAME_DEF_STMT (op2);
1771 : }
1772 :
1773 : // Bail if the chain leaves SBB.
1774 341812 : if (!stmt || gimple_bb (stmt) != sbb)
1775 : break;
1776 369005 : }
1777 :
1778 209221 : if (stmt != s)
1779 27465 : continue;
1780 :
1781 : // LHS_RANGE is now S's LHS as it is known in ORIG_BB.
1782 181756 : value_range op1_range (TREE_TYPE (s_handler.operand1 ()));
1783 181756 : value_range op2_range (TREE_TYPE (s_handler.operand2 ()));
1784 363512 : get_range_query (cfun)->range_on_entry (op1_range, orig_bb,
1785 : s_handler.operand1 ());
1786 363512 : get_range_query (cfun)->range_on_entry (op2_range, orig_bb,
1787 : s_handler.operand2 ());
1788 181756 : relation_kind r = s_handler.op1_op2_relation (lhs_range, op1_range,
1789 181756 : op2_range);
1790 181756 : if (reversed)
1791 41508 : r = relation_swap (r);
1792 181756 : relation_kind k = relation_intersect (result, r);
1793 181756 : if (k != VREL_UNDEFINED)
1794 181756 : result = k;
1795 210804 : }
1796 13254317 : return result;
1797 : }
1798 :
1799 : // Find a relation between SSA1 and SSA2 in the dominator tree starting with
1800 : // block BB
1801 :
1802 : relation_kind
1803 22938413 : dom_oracle::find_relation_dom (basic_block start_bb, tree ssa1, tree ssa2) const
1804 : {
1805 22938413 : relation_kind r;
1806 22938413 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1807 22938413 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1808 : // IF either name does not occur in a relation anywhere, there isn't one.
1809 22938413 : if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1810 : return VREL_VARYING;
1811 609016342 : for (basic_block bb = start_bb;
1812 631954755 : bb;
1813 609016342 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1814 : {
1815 611807841 : r = find_relation_block (bb->index, ssa1, ssa2);
1816 611807841 : if (r != VREL_VARYING)
1817 : return r;
1818 : }
1819 : return VREL_VARYING;
1820 : }
1821 :
1822 : // Starting with basic block BB, look for the next block in the dominator
1823 : // tree which contains a relation involving NAME. There can be more than one,
1824 : // and they are returned in the class local m_near vector. The block in which
1825 : // the relations are found are returned. If no relations are found, NULL is
1826 : // returned and the m_near vector is empty.
1827 :
1828 : basic_block
1829 80342562 : dom_oracle::nearest_relations (tree name, basic_block bb)
1830 : {
1831 80342562 : if (TREE_CODE (name) != SSA_NAME)
1832 : return NULL;
1833 :
1834 80342562 : unsigned v = SSA_NAME_VERSION (name);
1835 80342562 : if (!bitmap_bit_p (m_relation_set, v))
1836 : return NULL;
1837 :
1838 : // A relation involving NAME can only be registered in a block
1839 : // dominated by NAME's definition. Relations occurring *in* the def block
1840 : // are attached to the def block itself, so once that block has been
1841 : // examined there is nothing left to find and the walk can terminate.
1842 75937953 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1843 75937953 : bool at_def = false;
1844 :
1845 75937953 : m_near.truncate (0);
1846 1481551214 : for (; bb && !at_def; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1847 : {
1848 1378096807 : at_def = (bb == def_bb);
1849 :
1850 2756193614 : if (bb->index >= (int) m_relations.length ())
1851 1613 : continue;
1852 :
1853 1378095194 : const_bitmap bm = m_relations[bb->index].m_names;
1854 1378095194 : if (!bm || !bitmap_bit_p (bm, v))
1855 1329673689 : continue;
1856 :
1857 48421505 : for (relation_chain *ptr = m_relations[bb->index].m_head;
1858 180024359 : ptr; ptr = ptr->m_next)
1859 : {
1860 131602854 : if (v == SSA_NAME_VERSION (ptr->op1 ())
1861 131602854 : && !SSA_NAME_IN_FREE_LIST (ptr->op2 ()))
1862 33182558 : m_near.safe_push ({ ptr->kind (), ptr->op2 (), bb });
1863 98420296 : else if (v == SSA_NAME_VERSION (ptr->op2 ())
1864 98420296 : && !SSA_NAME_IN_FREE_LIST (ptr->op1 ()))
1865 43974290 : m_near.safe_push ({ relation_swap (ptr->kind ()),
1866 21987145 : ptr->op1 (), bb });
1867 : }
1868 :
1869 1378096811 : if (!m_near.is_empty ())
1870 : return bb;
1871 : }
1872 :
1873 : return NULL;
1874 : }
1875 :
1876 : // Record relation K between OP1 and OP2, discovered by a search in block BB,
1877 : // so subsequent queries in BB or anything it dominates find it directly.
1878 : // Use SEARCH_AND_MERGE_RELATION rather than CREATE_RELATION_IN_BB. The pair
1879 : // may already have a record in BB from an earlier query, in which case the
1880 : // two must be intersected rather than a second record created.
1881 :
1882 : void
1883 27323345 : dom_oracle::cache_relation (basic_block bb, relation_kind k, tree op1,
1884 : tree op2)
1885 : {
1886 27323345 : if (!bb || op1 == op2)
1887 : return;
1888 : // There is nothing useful to record for VARYING or UNDEFINED and
1889 : // Equivalences belong to the equivalence oracle.
1890 27323345 : if (k == VREL_VARYING || k == VREL_UNDEFINED || relation_equiv_p (k))
1891 : return;
1892 11320536 : search_and_merge_relation (bb, k, op1, op2);
1893 : }
1894 :
1895 : // Begin the search for SIDE at its root ROOT, whose equivalence set is
1896 : // EQUIV, in block BB. Every name equivalent to ROOT is an equally good
1897 : // starting point, so seed them all.
1898 :
1899 : void
1900 54646690 : dom_oracle::start_search (frontier_data &side, tree root, const_bitmap equiv,
1901 : basic_block bb)
1902 : {
1903 54646690 : side.m_root = root;
1904 :
1905 54646690 : unsigned root_v = SSA_NAME_VERSION (root);
1906 54646690 : m_worklist.safe_push ({ VREL_EQ, root, bb, side.m_rhs });
1907 54646690 : bitmap_set_bit (side.m_visited, root_v);
1908 54646690 : side.set_known (root_v, VREL_EQ);
1909 :
1910 54646690 : unsigned i;
1911 54646690 : bitmap_iterator bi;
1912 112774549 : EXECUTE_IF_SET_IN_BITMAP (equiv, 0, i, bi)
1913 : {
1914 : // Equivalences are maintained lazily, so ensure they are still
1915 : // valid before adding them to the frontier.
1916 58127859 : tree name = ssa_name (i);
1917 61609027 : if (i == root_v || !name || SSA_NAME_IN_FREE_LIST (name))
1918 54646691 : continue;
1919 3481168 : m_worklist.safe_push ({ VREL_EQ, name, bb, side.m_rhs });
1920 3481168 : bitmap_set_bit (side.m_visited, i);
1921 3481168 : side.set_known (i, VREL_EQ);
1922 : }
1923 54646690 : }
1924 :
1925 : // SIDE's root has been shown to be related to NAME by REL. Queue NAME for
1926 : // expansion starting at block BB.
1927 :
1928 : void
1929 17645158 : dom_oracle::add_to_frontier (frontier_data &side, tree name, relation_kind rel,
1930 : basic_block bb)
1931 : {
1932 17645158 : unsigned v = SSA_NAME_VERSION (name);
1933 17645158 : if (!side.visited_p (v))
1934 : {
1935 15793083 : bitmap_set_bit (side.m_visited, v);
1936 15793083 : side.set_known (v, rel);
1937 15793083 : m_worklist.safe_push ({ rel, name, bb, side.m_rhs });
1938 15793083 : return;
1939 : }
1940 :
1941 : // NAME already had a relation, so intersect the two and requeue NAME if
1942 : // there is an improvement.
1943 1852075 : relation_kind curr = side.known_relation (v);
1944 1852075 : relation_kind k = relation_intersect (curr, rel);
1945 1852075 : if (k != curr && k != VREL_UNDEFINED)
1946 : {
1947 32437 : side.set_known (v, k);
1948 32437 : m_worklist.safe_push ({ k, name, bb, side.m_rhs });
1949 : }
1950 : }
1951 :
1952 : // Expand worklist entry W, looking for a name the other side of the search
1953 : // has already reached. BB is the block the query was made in. Return true
1954 : // and set RESULT if a match was found. W is passed by value as
1955 : // add_to_frontier may realloc the vector.
1956 :
1957 : bool
1958 80342562 : dom_oracle::expand_frontier (frontier_element w, basic_block bb,
1959 : relation_kind &result)
1960 : {
1961 80342562 : frontier_data &self = w.rhs ? m_rhs_search : m_lhs_search;
1962 80342562 : frontier_data &other = w.rhs ? m_lhs_search : m_rhs_search;
1963 :
1964 80342562 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION))
1965 : {
1966 0 : fprintf (dump_file, " %s frontier expanding: ", w.rhs ? "RHS" : "LHS");
1967 0 : print_generic_expr (dump_file, w.name, TDF_SLIM);
1968 0 : fprintf (dump_file, " (rel: %d)\n", w.rel);
1969 : }
1970 :
1971 80342562 : basic_block found = nearest_relations (w.name, w.bb);
1972 80342562 : if (!found)
1973 : return false;
1974 :
1975 91960154 : for (unsigned i = 0; i < m_near.length (); ++i)
1976 : {
1977 : // nearest_relations sets m_near[i].rel as "w.name <rel> m_near.name",
1978 : // so composing it with "root <w.rel> w.name" gives "root <kind> next".
1979 54882340 : value_relation path (w.rel, self.m_root, w.name);
1980 54882340 : value_relation near_rel (m_near[i].rel, w.name, m_near[i].name);
1981 :
1982 54882340 : if (!path.apply_transitive (near_rel))
1983 25893497 : continue;
1984 :
1985 28988843 : relation_kind kind = path.kind ();
1986 28988843 : tree next = path.op2 ();
1987 28988843 : unsigned nv = SSA_NAME_VERSION (next);
1988 :
1989 : // If the other side has reached NEXT it knows "other_root <rel> next",
1990 : // which composes with what is known here to relate the two roots.
1991 28988843 : if (other.visited_p (nv))
1992 : {
1993 12102493 : relation_kind k
1994 12102493 : = relation_transitive (kind,
1995 : relation_swap (other.known_relation (nv)));
1996 : // If the result is not VARYING, we have a match.
1997 12102493 : if (k != VREL_VARYING)
1998 : {
1999 11343685 : result = w.rhs ? relation_swap (k) : k;
2000 11343685 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION))
2001 : {
2002 0 : fprintf (dump_file, " %s frontier found connection at: ",
2003 : w.rhs ? "RHS" : "LHS");
2004 0 : print_generic_expr (dump_file, next, TDF_SLIM);
2005 0 : fprintf (dump_file, ", combined relation: ");
2006 0 : print_relation (dump_file, result);
2007 0 : fputc ('\n', dump_file);
2008 : }
2009 11343685 : return true;
2010 : }
2011 : }
2012 :
2013 : // Add to this side's frontier if it has not visited NEXT yet.
2014 17645158 : add_to_frontier (self, next, kind, bb);
2015 : }
2016 :
2017 : // Keep searching for NAME in the dominator tree. Do not search past
2018 : // the def block as that is pointless. Do search the def block however
2019 : // as relations within the body of the block are stored there.
2020 : // Use whatever the latest known relation value is.
2021 37077814 : basic_block idom = get_immediate_dominator (CDI_DOMINATORS, found);
2022 37077814 : if (idom && gimple_bb (SSA_NAME_DEF_STMT (w.name)) != found)
2023 19636029 : m_worklist.safe_push ({ self.known_relation (SSA_NAME_VERSION (w.name)),
2024 : w.name, idom, w.rhs });
2025 :
2026 : return false;
2027 : }
2028 :
2029 : // Search for a relation between LHS and RHS in block BB or one of its
2030 : // dominators, expanding a frontier from both names until the two meet.
2031 : // LHS_EQUIV and RHS_EQUIV are the equivalence sets of LHS and RHS.
2032 :
2033 : relation_kind
2034 27323345 : dom_oracle::relation_search (basic_block bb, tree lhs, const_bitmap lhs_equiv,
2035 : tree rhs, const_bitmap rhs_equiv)
2036 : {
2037 : // Initialize both search frontiers.
2038 27323345 : start_search (m_lhs_search, lhs, lhs_equiv, bb);
2039 27323345 : start_search (m_rhs_search, rhs, rhs_equiv, bb);
2040 :
2041 27323345 : relation_kind result = VREL_VARYING;
2042 :
2043 : // Each expansion walks the dominator tree looking for the next block with
2044 : // a relation.
2045 27323345 : unsigned budget = param_transitive_relations_work_bound;
2046 :
2047 27323345 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION))
2048 : {
2049 0 : fprintf (dump_file, "Bidirectional relation search: ");
2050 0 : print_generic_expr (dump_file, lhs, TDF_SLIM);
2051 0 : fprintf (dump_file, " vs ");
2052 0 : print_generic_expr (dump_file, rhs, TDF_SLIM);
2053 0 : fprintf (dump_file, " in bb%d\n", bb ? bb->index : -1);
2054 : }
2055 :
2056 : // Expand until exhausted or until a connection is found.
2057 96322222 : while (m_wl_ix < m_worklist.length ())
2058 : {
2059 80362322 : if (!budget--)
2060 : {
2061 19760 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION))
2062 0 : fprintf (dump_file, " search budget exhausted\n");
2063 : break;
2064 : }
2065 :
2066 80342562 : if (expand_frontier (m_worklist[m_wl_ix++], bb, result))
2067 : break;
2068 : }
2069 :
2070 : // Clear search state for reuse.
2071 27323345 : m_worklist.truncate (0);
2072 27323345 : m_wl_ix = 0;
2073 27323345 : m_lhs_search.clear_search ();
2074 27323345 : m_rhs_search.clear_search ();
2075 :
2076 : // Check to see if any new relations can be formed by recomputing an
2077 : // expression using LHS and RHS.
2078 : // This call must come after the worklists are cleared above. The call
2079 : // may invoke range_on_entry which may trigger another relation search,
2080 : // and thus the current search must be cleared before making this call.
2081 27323345 : relation_kind rel = recomputed_relation (bb, lhs, rhs);
2082 :
2083 27323345 : if (rel != VREL_VARYING)
2084 : {
2085 113544 : rel = relation_intersect (result, rel);
2086 113544 : if (rel != VREL_UNDEFINED)
2087 113544 : result = rel;
2088 : }
2089 :
2090 : // Record whatever was found so the next query for this pair is a direct
2091 : // lookup rather than another search.
2092 27323345 : cache_relation (bb, result, lhs, rhs);
2093 :
2094 27323345 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION)
2095 0 : && result != VREL_VARYING)
2096 : {
2097 0 : fprintf (dump_file, " relation_search returning: ");
2098 0 : print_generic_expr (dump_file, lhs, TDF_SLIM);
2099 0 : print_relation (dump_file, result);
2100 0 : print_generic_expr (dump_file, rhs, TDF_SLIM);
2101 0 : fprintf (dump_file, "\n");
2102 : }
2103 :
2104 27323345 : return result;
2105 : }
2106 :
2107 : // Query if there is a relation between SSA1 and SS2 in block BB or a
2108 : // dominator of BB
2109 :
2110 : relation_kind
2111 121123036 : dom_oracle::query (basic_block bb, tree ssa1, tree ssa2)
2112 : {
2113 121123036 : relation_kind kind;
2114 121123036 : unsigned v1 = SSA_NAME_VERSION (ssa1);
2115 121123036 : unsigned v2 = SSA_NAME_VERSION (ssa2);
2116 121123036 : if (v1 == v2)
2117 : return VREL_EQ;
2118 :
2119 : // If v1 or v2 do not have any relations or equivalences, a partial
2120 : // equivalence is the only possibility.
2121 203922600 : if ((!bitmap_bit_p (m_relation_set, v1) && !has_equiv_p (v1))
2122 124870868 : || (!bitmap_bit_p (m_relation_set, v2) && !has_equiv_p (v2)))
2123 93549540 : return partial_equiv (ssa1, ssa2);
2124 :
2125 : // Check for equivalence first. They must be in each equivalency set.
2126 27471756 : const_bitmap equiv1 = equiv_set (ssa1, bb);
2127 27471756 : const_bitmap equiv2 = equiv_set (ssa2, bb);
2128 27471756 : if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
2129 : return VREL_EQ;
2130 :
2131 : // A statement such as c = a & 0xff makes a partial equivalence between
2132 : // c and a, and an ordinary comparison can then relate the same pair.
2133 : // If both exist, prefer the relation, so look for that first.
2134 27323345 : kind = relation_search (bb, ssa1, equiv1, ssa2, equiv2);
2135 :
2136 : // Finally look for partial equivalences.
2137 27323345 : if (kind == VREL_VARYING)
2138 15978261 : kind = partial_equiv (ssa1, ssa2);
2139 : return kind;
2140 : }
2141 :
2142 : // Dump all the relations in block BB to file F.
2143 :
2144 : void
2145 257 : dom_oracle::dump (FILE *f, basic_block bb) const
2146 : {
2147 257 : equiv_oracle::dump (f,bb);
2148 :
2149 514 : if (bb->index >= (int)m_relations.length ())
2150 218 : return;
2151 257 : if (!m_relations[bb->index].m_names)
2152 : return;
2153 :
2154 39 : value_relation vr;
2155 90 : FOR_EACH_RELATION_BB (this, bb, vr)
2156 : {
2157 51 : fprintf (f, "Relational : ");
2158 51 : vr.dump (f);
2159 51 : fprintf (f, "\n");
2160 : }
2161 : }
2162 :
2163 : // Dump all the relations known to file F.
2164 :
2165 : void
2166 0 : dom_oracle::dump (FILE *f) const
2167 : {
2168 0 : fprintf (f, "Relation dump\n");
2169 0 : for (unsigned i = 0; i < m_relations.length (); i++)
2170 0 : if (BASIC_BLOCK_FOR_FN (cfun, i))
2171 : {
2172 0 : fprintf (f, "BB%d\n", i);
2173 0 : dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
2174 : }
2175 0 : }
2176 :
2177 : void
2178 0 : relation_oracle::debug () const
2179 : {
2180 0 : dump (stderr);
2181 0 : }
2182 :
2183 9476632 : path_oracle::path_oracle (relation_oracle *oracle)
2184 : {
2185 9476632 : set_root_oracle (oracle);
2186 9476632 : bitmap_obstack_initialize (&m_bitmaps);
2187 9476632 : obstack_init (&m_chain_obstack);
2188 :
2189 : // Initialize header records.
2190 9476632 : m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
2191 9476632 : m_equiv.m_bb = NULL;
2192 9476632 : m_equiv.m_next = NULL;
2193 9476632 : m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
2194 9476632 : m_relations.m_head = NULL;
2195 9476632 : m_killed_defs = BITMAP_ALLOC (&m_bitmaps);
2196 9476632 : }
2197 :
2198 18953264 : path_oracle::~path_oracle ()
2199 : {
2200 9476632 : obstack_free (&m_chain_obstack, NULL);
2201 9476632 : bitmap_obstack_release (&m_bitmaps);
2202 18953264 : }
2203 :
2204 : // Clear any range info and relations associated with NAME.
2205 :
2206 : void
2207 0 : path_oracle::clear (tree name)
2208 : {
2209 0 : if (m_root)
2210 0 : m_root->clear (name);
2211 :
2212 0 : m_relations.clear (name);
2213 :
2214 0 : unsigned v = SSA_NAME_VERSION (name);
2215 0 : equiv_chain *ptr = m_equiv.find (v);
2216 0 : if (ptr)
2217 0 : bitmap_clear_bit (ptr->m_names, v);
2218 0 : }
2219 :
2220 : // Return the equiv set for SSA, and if there isn't one, check for equivs
2221 : // starting in block BB.
2222 :
2223 : const_bitmap
2224 144630362 : path_oracle::equiv_set (tree ssa, basic_block bb)
2225 : {
2226 : // Check the list first.
2227 144630362 : equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
2228 144630362 : if (ptr)
2229 77952876 : return ptr->m_names;
2230 :
2231 : // Otherwise defer to the root oracle.
2232 66677486 : if (m_root)
2233 60265208 : return m_root->equiv_set (ssa, bb);
2234 :
2235 : // Allocate a throw away bitmap if there isn't a root oracle.
2236 6412278 : bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
2237 6412278 : bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
2238 6412278 : return tmp;
2239 : }
2240 :
2241 : // Register an equivalence between SSA1 and SSA2 resolving unknowns from
2242 : // block BB. Return false if no new equivalence was added.
2243 :
2244 : bool
2245 8941478 : path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
2246 : {
2247 8941478 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
2248 8941478 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
2249 :
2250 : // Check if they are the same set, if so, we're done.
2251 8941478 : if (bitmap_equal_p (equiv_1, equiv_2))
2252 : return false;
2253 :
2254 : // Don't mess around, simply create a new record and insert it first.
2255 8922404 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
2256 8922404 : valid_equivs (b, equiv_1, bb);
2257 8922404 : valid_equivs (b, equiv_2, bb);
2258 :
2259 8922404 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
2260 : sizeof (equiv_chain));
2261 8922404 : ptr->m_names = b;
2262 8922404 : ptr->m_bb = NULL;
2263 8922404 : ptr->m_next = m_equiv.m_next;
2264 8922404 : m_equiv.m_next = ptr;
2265 8922404 : bitmap_ior_into (m_equiv.m_names, b);
2266 8922404 : return true;
2267 : }
2268 :
2269 : // Register killing definition of an SSA_NAME.
2270 :
2271 : void
2272 63273529 : path_oracle::killing_def (tree ssa)
2273 : {
2274 63273529 : if (dump_file && (dump_flags & TDF_DETAILS))
2275 : {
2276 990 : fprintf (dump_file, " Registering killing_def (path_oracle) ");
2277 990 : print_generic_expr (dump_file, ssa, TDF_SLIM);
2278 990 : fprintf (dump_file, "\n");
2279 : }
2280 :
2281 63273529 : unsigned v = SSA_NAME_VERSION (ssa);
2282 :
2283 63273529 : bitmap_set_bit (m_killed_defs, v);
2284 63273529 : bitmap_set_bit (m_equiv.m_names, v);
2285 :
2286 : // Now add an equivalency with itself so we don't look to the root oracle.
2287 63273529 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
2288 63273529 : bitmap_set_bit (b, v);
2289 63273529 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
2290 : sizeof (equiv_chain));
2291 63273529 : ptr->m_names = b;
2292 63273529 : ptr->m_bb = NULL;
2293 63273529 : ptr->m_next = m_equiv.m_next;
2294 63273529 : m_equiv.m_next = ptr;
2295 :
2296 : // Walk the relation list and remove SSA from any relations.
2297 63273529 : if (!bitmap_bit_p (m_relations.m_names, v))
2298 : return;
2299 :
2300 413421 : bitmap_clear_bit (m_relations.m_names, v);
2301 413421 : relation_chain **prev = &(m_relations.m_head);
2302 413421 : relation_chain *next = NULL;
2303 941407 : for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
2304 : {
2305 527986 : gcc_checking_assert (*prev == ptr);
2306 527986 : next = ptr->m_next;
2307 527986 : if (SSA_NAME_VERSION (ptr->op1 ()) == v
2308 527986 : || SSA_NAME_VERSION (ptr->op2 ()) == v)
2309 341628 : *prev = ptr->m_next;
2310 : else
2311 186358 : prev = &(ptr->m_next);
2312 : }
2313 : }
2314 :
2315 : // Register relation K between SSA1 and SSA2, resolving unknowns by
2316 : // querying from BB. Return false if no new relation is registered.
2317 :
2318 : bool
2319 32424159 : path_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
2320 : {
2321 : // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
2322 : // and no other relation makes sense.
2323 32424159 : if (ssa1 == ssa2)
2324 : return false;
2325 :
2326 : // Partial equivalences are tracked in the root equivalence oracle rather
2327 : // than on the path. Registering a partial equivalence in the path would
2328 : // cause normal relations to collapse to VARYING.
2329 32379030 : if (relation_partial_equiv_p (k))
2330 : return false;
2331 :
2332 28502918 : relation_kind curr = query (bb, ssa1, ssa2);
2333 : // Likewise, a partial equivalency result should not be combined with K
2334 : // or the result drops to VARYING.
2335 28502918 : if (curr != VREL_VARYING && !relation_partial_equiv_p (curr))
2336 4283054 : k = relation_intersect (curr, k);
2337 :
2338 : // Do not register an impossible relation.
2339 28502918 : if (k == VREL_UNDEFINED)
2340 : return false;
2341 :
2342 26199162 : bool ret;
2343 26199162 : if (k == VREL_EQ)
2344 8941478 : ret = register_equiv (bb, ssa1, ssa2);
2345 : else
2346 : {
2347 17257684 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
2348 17257684 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
2349 17257684 : relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
2350 : sizeof (relation_chain));
2351 17257684 : ptr->set_relation (k, ssa1, ssa2);
2352 17257684 : ptr->m_next = m_relations.m_head;
2353 17257684 : m_relations.m_head = ptr;
2354 17257684 : ret = true;
2355 : }
2356 :
2357 26199162 : if (ret && dump_file && (dump_flags & TDF_DETAILS))
2358 : {
2359 304 : value_relation vr (k, ssa1, ssa2);
2360 304 : fprintf (dump_file, " Registering value_relation (path_oracle) ");
2361 304 : vr.dump (dump_file);
2362 304 : fprintf (dump_file, " (root: bb%d)\n", bb->index);
2363 : }
2364 : return ret;
2365 : }
2366 :
2367 : // Query for a relationship between equiv set B1 and B2, resolving unknowns
2368 : // starting at block BB.
2369 :
2370 : relation_kind
2371 53195954 : path_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
2372 : {
2373 53195954 : if (bitmap_equal_p (b1, b2))
2374 : return VREL_EQ;
2375 :
2376 53195954 : relation_kind k = m_relations.find_relation (b1, b2);
2377 :
2378 : // Do not look at the root oracle for names that have been killed
2379 : // along the path.
2380 53195954 : if (bitmap_intersect_p (m_killed_defs, b1)
2381 53195954 : || bitmap_intersect_p (m_killed_defs, b2))
2382 : return k;
2383 :
2384 : // Query the root oracle for relations with path local equivalencies.
2385 14360606 : if (k == VREL_VARYING && m_root)
2386 11958365 : k = m_root->query (bb, b1, b2);
2387 :
2388 : return k;
2389 : }
2390 :
2391 : // Query for a relationship between SSA1 and SSA2, resolving unknowns
2392 : // starting at block BB.
2393 :
2394 : relation_kind
2395 53907033 : path_oracle::query (basic_block bb, tree ssa1, tree ssa2)
2396 : {
2397 53907033 : unsigned v1 = SSA_NAME_VERSION (ssa1);
2398 53907033 : unsigned v2 = SSA_NAME_VERSION (ssa2);
2399 :
2400 53907033 : if (v1 == v2)
2401 : return VREL_EQ;
2402 :
2403 53812810 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
2404 53812810 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
2405 53812810 : if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
2406 : return VREL_EQ;
2407 :
2408 53195954 : relation_kind rel = query (bb, equiv_1, equiv_2);
2409 :
2410 : // If the path relation query fails, check for relations in the root oracle.
2411 53195954 : if (rel == VREL_VARYING && m_root)
2412 46389851 : rel = m_root->query (bb, ssa1, ssa2);
2413 : return rel;
2414 : }
2415 :
2416 : // Reset any relations registered on this path. ORACLE is the root
2417 : // oracle to use.
2418 :
2419 : void
2420 40769366 : path_oracle::reset_path (relation_oracle *oracle)
2421 : {
2422 40769366 : set_root_oracle (oracle);
2423 40769366 : m_equiv.m_next = NULL;
2424 40769366 : bitmap_clear (m_equiv.m_names);
2425 40769366 : m_relations.m_head = NULL;
2426 40769366 : bitmap_clear (m_relations.m_names);
2427 40769366 : bitmap_clear (m_killed_defs);
2428 40769366 : }
2429 :
2430 : // Dump relation in basic block... Do nothing here.
2431 :
2432 : void
2433 0 : path_oracle::dump (FILE *, basic_block) const
2434 : {
2435 0 : }
2436 :
2437 : // Dump the relations and equivalencies found in the path.
2438 :
2439 : void
2440 0 : path_oracle::dump (FILE *f) const
2441 : {
2442 0 : equiv_chain *ptr = m_equiv.m_next;
2443 0 : relation_chain *ptr2 = m_relations.m_head;
2444 :
2445 0 : if (ptr || ptr2)
2446 0 : fprintf (f, "\npath_oracle:\n");
2447 :
2448 0 : for (; ptr; ptr = ptr->m_next)
2449 0 : ptr->dump (f);
2450 :
2451 0 : for (; ptr2; ptr2 = ptr2->m_next)
2452 : {
2453 0 : fprintf (f, "Relational : ");
2454 0 : ptr2->dump (f);
2455 0 : fprintf (f, "\n");
2456 : }
2457 0 : }
2458 :
2459 : // ------------------------------------------------------------------------
2460 : // EQUIV iterator. Although we have bitmap iterators, don't expose that it
2461 : // is currently a bitmap. Use an export iterator to hide future changes.
2462 :
2463 : // Construct a basic iterator over an equivalence bitmap.
2464 :
2465 55378512 : equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle,
2466 : basic_block bb, tree name,
2467 : bool full, bool partial)
2468 : {
2469 55378512 : m_name = name;
2470 55378512 : m_oracle = oracle;
2471 55378512 : m_pe = partial ? oracle->partial_equiv_set (name) : NULL;
2472 55378512 : m_bm = NULL;
2473 55378512 : if (full)
2474 55378512 : m_bm = oracle->equiv_set (name, bb);
2475 55378512 : if (!m_bm && m_pe)
2476 0 : m_bm = m_pe->members;
2477 55378512 : if (m_bm)
2478 55378511 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
2479 55378512 : }
2480 :
2481 : // Move to the next export bitmap spot.
2482 :
2483 : void
2484 73123381 : equiv_relation_iterator::next ()
2485 : {
2486 73123381 : bmp_iter_next (&m_bi, &m_y);
2487 73123381 : }
2488 :
2489 : // Fetch the name of the next export in the export list. Return NULL if
2490 : // iteration is done.
2491 :
2492 : tree
2493 66594421 : equiv_relation_iterator::get_name (relation_kind *rel)
2494 : {
2495 73123224 : if (!m_bm)
2496 : return NULL_TREE;
2497 :
2498 135030695 : while (bmp_iter_set (&m_bi, &m_y))
2499 : {
2500 : // Do not return self.
2501 73123381 : tree t = ssa_name (m_y);
2502 73123381 : if (t && t != m_name)
2503 : {
2504 11215925 : relation_kind k = VREL_EQ;
2505 11215925 : if (m_pe && m_bm == m_pe->members)
2506 : {
2507 8325325 : const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t);
2508 8325325 : if (equiv_pe && equiv_pe->members == m_pe->members)
2509 8325309 : k = pe_min (m_pe->code, equiv_pe->code);
2510 : else
2511 : k = VREL_VARYING;
2512 : }
2513 8325325 : if (relation_equiv_p (k))
2514 : {
2515 11215909 : if (rel)
2516 11215909 : *rel = k;
2517 : return t;
2518 : }
2519 : }
2520 61907472 : next ();
2521 : }
2522 :
2523 : // Process partial equivs after full equivs if both were requested.
2524 61907314 : if (m_pe && m_bm != m_pe->members)
2525 : {
2526 55378511 : m_bm = m_pe->members;
2527 55378511 : if (m_bm)
2528 : {
2529 : // Recursively call back to process First PE.
2530 6528803 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
2531 6528803 : return get_name (rel);
2532 : }
2533 : }
2534 : return NULL_TREE;
2535 : }
2536 :
2537 : #if CHECKING_P
2538 : #include "selftest.h"
2539 :
2540 : namespace selftest
2541 : {
2542 : void
2543 4 : relation_tests ()
2544 : {
2545 : // rr_*_table tables use unsigned char rather than relation_kind.
2546 4 : ASSERT_LT (VREL_LAST, UCHAR_MAX);
2547 52 : for (relation_kind r1 = VREL_VARYING; r1 < VREL_LAST;
2548 48 : r1 = relation_kind (r1 + 1))
2549 : {
2550 : // Swapping the operands twice is a no-op.
2551 48 : ASSERT_EQ (relation_swap (relation_swap (r1)), r1);
2552 :
2553 : // VARYING intersect X is X.
2554 : // UNDEFINED intersect X is UNDEFINED.
2555 48 : ASSERT_EQ (relation_intersect (VREL_VARYING, r1), r1);
2556 48 : ASSERT_EQ (relation_intersect (VREL_UNDEFINED, r1), VREL_UNDEFINED);
2557 :
2558 : // UNDEFINED union X is X.
2559 : // VARYING union X is VARYING.
2560 48 : ASSERT_EQ (relation_union (VREL_UNDEFINED, r1), r1);
2561 48 : ASSERT_EQ (relation_union (VREL_VARYING, r1), VREL_VARYING);
2562 :
2563 : // Verify commutativity of relation_intersect and relation_union.
2564 624 : for (relation_kind r2 = VREL_VARYING; r2 < VREL_LAST;
2565 576 : r2 = relation_kind (r2 + 1))
2566 : {
2567 576 : ASSERT_EQ (relation_intersect (r1, r2), relation_intersect (r2, r1));
2568 576 : ASSERT_EQ (relation_union (r1, r2), relation_union (r2, r1));
2569 : }
2570 : }
2571 :
2572 : // Verify partial equivalence properties.
2573 20 : for (relation_kind r1 = VREL_PE8; r1 <= VREL_PE64;
2574 16 : r1 = relation_kind (r1 + 1))
2575 : {
2576 16 : ASSERT_EQ (relation_swap (r1), r1);
2577 16 : ASSERT_EQ (relation_intersect (VREL_EQ, r1), VREL_EQ);
2578 16 : ASSERT_EQ (relation_union (VREL_EQ, r1), r1);
2579 16 : ASSERT_EQ (relation_transitive (VREL_EQ, r1), r1);
2580 16 : ASSERT_EQ (relation_transitive (r1, VREL_EQ), r1);
2581 80 : for (relation_kind r2 = VREL_PE8; r2 <= VREL_PE64;
2582 64 : r2 = relation_kind (r2 + 1))
2583 : {
2584 64 : ASSERT_EQ (relation_intersect (r1, r2), MAX (r1, r2));
2585 64 : ASSERT_EQ (relation_union (r1, r2), pe_min (r1, r2));
2586 64 : ASSERT_EQ (relation_transitive (r1, r2), pe_min (r1, r2));
2587 : }
2588 : }
2589 4 : }
2590 :
2591 : } // namespace selftest
2592 :
2593 : #endif // CHECKING_P
|
