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 39942 : print_relation (FILE *f, relation_kind rel)
43 : {
44 39942 : fprintf (f, " %s ", kind_string[rel]);
45 39942 : }
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 19222312 : relation_swap (relation_kind r)
71 : {
72 19222312 : 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 102429256 : relation_intersect (relation_kind r1, relation_kind r2)
134 : {
135 102429256 : 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 91767068 : relation_union (relation_kind r1, relation_kind r2)
193 : {
194 91767068 : 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 8932348 : relation_transitive (relation_kind r1, relation_kind r2)
257 : {
258 8932348 : 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 2027519 : adjust_equivalence_range (vrange &range)
267 : {
268 2027519 : if (range.undefined_p () || !is_a<frange> (range))
269 1994126 : return;
270 :
271 33393 : frange fr = as_a<frange> (range);
272 : // If range includes 0 make sure both signs of zero are included.
273 33393 : if (fr.contains_p (dconst0) || fr.contains_p (dconstm0))
274 : {
275 16943 : frange zeros (range.type (), dconstm0, dconst0);
276 16943 : range.union_ (zeros);
277 16943 : }
278 33393 : }
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 23474350 : relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
285 : {
286 23474350 : unsigned i;
287 23474350 : bitmap_iterator bi;
288 49043611 : EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
289 : {
290 25569261 : tree ssa = ssa_name (i);
291 51138522 : if (ssa && !SSA_NAME_IN_FREE_LIST (ssa))
292 : {
293 25569261 : const_bitmap ssa_equiv = equiv_set (ssa, bb);
294 25569261 : if (ssa_equiv == equivs)
295 25281952 : bitmap_set_bit (b, i);
296 : }
297 : }
298 23474350 : }
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 114157059 : relation_oracle::query (gimple *s, tree ssa1, tree ssa2)
306 : {
307 114157059 : if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
308 : return VREL_VARYING;
309 42680367 : 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 50963032 : relation_oracle::query (edge e, tree ssa1, tree ssa2)
318 : {
319 50963032 : basic_block bb;
320 50963032 : 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 37640499 : if (!single_pred_p (e->dest))
327 35945870 : bb = e->src;
328 : else
329 : bb = e->dest;
330 :
331 37640499 : 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 199470529 : equiv_chain::find (unsigned ssa)
348 : {
349 199470529 : 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 199470529 : if (bitmap_bit_p (m_names, ssa))
353 : {
354 229527282 : for (ptr = m_next; ptr; ptr = ptr->m_next)
355 229527282 : if (bitmap_bit_p (ptr->m_names, ssa))
356 : break;
357 : }
358 199470529 : 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 27398343 : equiv_oracle::equiv_oracle ()
388 : {
389 27398343 : bitmap_obstack_initialize (&m_bitmaps);
390 27398343 : m_equiv.create (0);
391 27398343 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
392 27398343 : m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
393 27398343 : bitmap_tree_view (m_equiv_set);
394 27398343 : obstack_init (&m_chain_obstack);
395 27398343 : m_name_info.create (0);
396 54796686 : m_name_info.safe_grow_cleared (num_ssa_names + 1);
397 27398343 : m_partial.create (0);
398 54796686 : 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 27398343 : m_lhs_equiv_set_p = BITMAP_ALLOC (&m_bitmaps);
402 27398343 : bitmap_tree_view (m_lhs_equiv_set_p);
403 27398343 : }
404 :
405 : // Destruct an equivalency oracle.
406 :
407 27398343 : equiv_oracle::~equiv_oracle ()
408 : {
409 27398343 : m_partial.release ();
410 27398343 : m_name_info.release ();
411 27398343 : obstack_free (&m_chain_obstack, NULL);
412 27398343 : m_equiv.release ();
413 27398343 : bitmap_obstack_release (&m_bitmaps);
414 27398343 : }
415 :
416 : // Add a partial equivalence R between OP1 and OP2. Return false if no
417 : // new relation is added.
418 :
419 : bool
420 10186395 : equiv_oracle::add_partial_equiv (relation_kind r, tree op1, tree op2)
421 : {
422 10186395 : int v1 = SSA_NAME_VERSION (op1);
423 10186395 : int v2 = SSA_NAME_VERSION (op2);
424 10186395 : int prec2 = TYPE_PRECISION (TREE_TYPE (op2));
425 10186395 : int bits = pe_to_bits (r);
426 10186395 : gcc_checking_assert (bits && prec2 >= bits);
427 :
428 20372790 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
429 458 : m_partial.safe_grow_cleared (num_ssa_names + 1);
430 20372790 : gcc_checking_assert (v1 < (int)m_partial.length ()
431 : && v2 < (int)m_partial.length ());
432 :
433 10186395 : pe_slice &pe1 = m_partial[v1];
434 10186395 : pe_slice &pe2 = m_partial[v2];
435 :
436 10186395 : 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 189 : if (pe2.members)
442 : return false;
443 : // If there are no uses of op2, do not register.
444 166 : 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 166 : pe2.code = pe_min (r, pe1.code);
449 166 : pe2.ssa_base = op2;
450 166 : pe2.members = pe1.members;
451 166 : bitmap_iterator bi;
452 166 : unsigned x;
453 502 : EXECUTE_IF_SET_IN_BITMAP (pe1.members, 0, x, bi)
454 : {
455 336 : m_partial[x].ssa_base = op2;
456 336 : m_partial[x].code = pe_min (m_partial[x].code, pe2.code);
457 : }
458 166 : bitmap_set_bit (pe1.members, v2);
459 166 : return true;
460 : }
461 10186206 : if (pe2.members)
462 : {
463 : // If there are no uses of op1, do not register.
464 725525 : if (has_zero_uses (op1))
465 : return false;
466 715038 : 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 715038 : pe1.code = pe_min (r, pe2.code);
470 715038 : pe1.members = pe2.members;
471 715038 : bitmap_set_bit (pe1.members, v1);
472 : }
473 : else
474 : {
475 : // If there are no uses of either operand, do not register.
476 9460681 : 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 9373276 : pe2.code = bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2)));
480 9373276 : if (pe2.code == VREL_VARYING)
481 : return false;
482 9319156 : pe2.ssa_base = op2;
483 9319156 : pe2.members = BITMAP_ALLOC (&m_bitmaps);
484 9319156 : bitmap_set_bit (pe2.members, v2);
485 9319156 : pe1.ssa_base = op2;
486 9319156 : pe1.code = r;
487 9319156 : pe1.members = pe2.members;
488 9319156 : 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 60496416 : equiv_oracle::partial_equiv_set (tree name)
498 : {
499 60496416 : int v = SSA_NAME_VERSION (name);
500 120992832 : if (v >= (int)m_partial.length ())
501 : return NULL;
502 60496416 : 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 92656580 : equiv_oracle::partial_equiv (tree ssa1, tree ssa2, tree *base) const
511 : {
512 92656580 : int v1 = SSA_NAME_VERSION (ssa1);
513 92656580 : int v2 = SSA_NAME_VERSION (ssa2);
514 :
515 185313160 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
516 : return VREL_VARYING;
517 :
518 92656508 : const pe_slice &pe1 = m_partial[v1];
519 92656508 : const pe_slice &pe2 = m_partial[v2];
520 92656508 : if (pe1.members && pe2.members == pe1.members)
521 : {
522 1682 : if (base)
523 0 : *base = pe1.ssa_base;
524 1682 : return pe_min (pe1.code, pe2.code);
525 : }
526 : return VREL_VARYING;
527 : }
528 :
529 : void
530 18086898 : equiv_oracle::register_equiv_block (unsigned v, unsigned bbi)
531 : {
532 18086898 : if (v >= m_name_info.length ())
533 50 : m_name_info.safe_grow_cleared (num_ssa_names + 1);
534 :
535 18086898 : if (!m_name_info[v].m_block_list)
536 7479965 : m_name_info[v].m_block_list = BITMAP_ALLOC (&m_bitmaps);
537 :
538 18086898 : bitmap_set_bit (m_name_info[v].m_block_list, bbi);
539 18086898 : }
540 :
541 : void
542 12999526 : equiv_oracle::register_equiv_block (const_bitmap names, basic_block bb)
543 : {
544 12999526 : bitmap_iterator bi;
545 12999526 : unsigned v;
546 :
547 31069885 : EXECUTE_IF_SET_IN_BITMAP (names, 0, v, bi)
548 18070359 : register_equiv_block (v, bb->index);
549 12999526 : }
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 169518617 : equiv_oracle::equiv_set (tree ssa, basic_block bb)
556 : {
557 : // Search the dominator tree for an equivalency.
558 169518617 : equiv_chain *equiv = find_equiv_dom (ssa, bb);
559 169518617 : if (equiv)
560 19232117 : return equiv->m_names;
561 :
562 : // Otherwise return a cached equiv set containing just this SSA.
563 150286500 : unsigned v = SSA_NAME_VERSION (ssa);
564 150286500 : if (v >= m_name_info.length ())
565 220 : m_name_info.safe_grow_cleared (num_ssa_names + 1);
566 :
567 150286500 : if (!m_name_info[v].m_self_equiv)
568 : {
569 36775865 : m_name_info[v].m_self_equiv = BITMAP_ALLOC (&m_bitmaps);
570 36775865 : bitmap_set_bit (m_name_info[v].m_self_equiv, v);
571 : }
572 150286500 : 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 141962471 : equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
605 : {
606 283924942 : if (bb >= (int)m_equiv.length () || !m_equiv[bb])
607 : return NULL;
608 :
609 59710817 : 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 185210990 : equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
617 : {
618 185210990 : 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 185210990 : 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 144191975 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
627 : {
628 141962471 : equiv_chain *ptr = find_equiv_block (v, bb->index);
629 141962471 : 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 77462 : equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
639 : {
640 : // V will have an equivalency now.
641 77462 : bitmap_set_bit (m_equiv_set, v);
642 :
643 : // If that equiv chain is in this block, simply use it.
644 77462 : if (equiv->m_bb == bb)
645 : {
646 16539 : bitmap_set_bit (equiv->m_names, v);
647 16539 : bitmap_set_bit (m_equiv[bb->index]->m_names, v);
648 : // Add BB to V.
649 16539 : register_equiv_block (v, bb->index);
650 16539 : 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 60923 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
656 60923 : valid_equivs (b, equiv->m_names, bb);
657 60923 : bitmap_set_bit (b, v);
658 : // Add BB to the all the equiv names.
659 60923 : register_equiv_block (b, bb);
660 60923 : 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 4059834 : 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 4059834 : if (equiv_1->m_bb == bb)
674 : {
675 2261332 : 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 2261332 : if (equiv_2->m_bb == bb)
679 382369 : bitmap_clear (equiv_2->m_names);
680 : else
681 : {
682 : // Ensure the new names are in the summary for BB.
683 1878963 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
684 : // Add BB to the names in equiv2.
685 1878963 : 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 1798502 : if (equiv_2->m_bb == bb)
691 : {
692 2455 : valid_equivs (equiv_2->m_names, equiv_1->m_names, bb);
693 : // Ensure the new names are in the summary.
694 2455 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
695 : // Add BB to the names in equiv1.
696 2455 : register_equiv_block (equiv_1->m_names, bb);
697 2455 : return NULL;
698 : }
699 :
700 : // At this point, neither equivalence is from this block.
701 1796047 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
702 1796047 : valid_equivs (b, equiv_1->m_names, bb);
703 1796047 : valid_equivs (b, equiv_2->m_names, bb);
704 : // Add BB to the all the equiv names.
705 1796047 : register_equiv_block (b, bb);
706 1796047 : 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 7479965 : equiv_oracle::register_initial_def (tree ssa)
715 : {
716 7479965 : if (SSA_NAME_IS_DEFAULT_DEF (ssa))
717 : return;
718 7394104 : basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
719 :
720 : // If defining stmt is not in the IL, simply return.
721 7394104 : if (!bb)
722 : return;
723 7394103 : gcc_checking_assert (!find_equiv_dom (ssa, bb));
724 :
725 7394103 : unsigned v = SSA_NAME_VERSION (ssa);
726 7394103 : bitmap_set_bit (m_equiv_set, v);
727 7394103 : bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps);
728 7394103 : bitmap_set_bit (equiv_set, v);
729 7394103 : add_equiv_to_block (bb, equiv_set);
730 : }
731 :
732 : // Clear the equivalence lists and partial equivalencs for NAME.
733 :
734 : void
735 440 : equiv_oracle::clear (tree name)
736 : {
737 440 : unsigned v = SSA_NAME_VERSION (name);
738 : // Remove NAME from any blocks it is an equivalence in.
739 440 : if (bitmap_bit_p (m_equiv_set, v))
740 : {
741 17 : gcc_checking_assert (m_name_info[v].m_block_list);
742 17 : bitmap_iterator bi;
743 17 : unsigned bbi;
744 :
745 34 : EXECUTE_IF_SET_IN_BITMAP (m_name_info[v].m_block_list, 0, bbi, bi)
746 : {
747 17 : if (bbi >= m_equiv.length ())
748 : break;
749 17 : if (!m_equiv[bbi])
750 0 : continue;
751 17 : equiv_chain *ptr = m_equiv[bbi]->find (v);
752 17 : if (ptr)
753 : {
754 17 : bitmap_clear_bit (ptr->m_names, v);
755 17 : bitmap_clear_bit (m_equiv[bbi]->m_names, v);
756 : }
757 : }
758 17 : bitmap_clear_bit (m_equiv_set, v);
759 17 : bitmap_clear (m_name_info[v].m_block_list);
760 : }
761 : // Eliminate any partial equivs.
762 440 : if (v < m_partial.length ())
763 440 : m_partial[v].members = NULL;
764 440 : }
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 14335530 : equiv_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
777 : {
778 : // Process partial equivalencies.
779 14335530 : if (relation_partial_equiv_p (k))
780 10186395 : return add_partial_equiv (k, ssa1, ssa2);
781 :
782 : // Only handle equality relations.
783 4149135 : if (k != VREL_EQ)
784 : return false;
785 :
786 4149135 : unsigned v1 = SSA_NAME_VERSION (ssa1);
787 4149135 : 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 4149135 : if (!bitmap_bit_p (m_equiv_set, v1))
792 3981371 : register_initial_def (ssa1);
793 4149135 : if (!bitmap_bit_p (m_equiv_set, v2))
794 3498594 : register_initial_def (ssa2);
795 :
796 4149135 : equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
797 4149135 : equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
798 :
799 : // Check if they are the same set
800 4149135 : if (equiv_1 && equiv_1 == equiv_2)
801 : return false;
802 :
803 4147361 : bitmap equiv_set;
804 :
805 : // Case where we have 2 SSA_NAMEs that are not in any set.
806 4147361 : if (!equiv_1 && !equiv_2)
807 : {
808 10065 : bitmap_set_bit (m_equiv_set, v1);
809 10065 : bitmap_set_bit (m_equiv_set, v2);
810 :
811 10065 : equiv_set = BITMAP_ALLOC (&m_bitmaps);
812 10065 : bitmap_set_bit (equiv_set, v1);
813 10065 : bitmap_set_bit (equiv_set, v2);
814 : }
815 4137296 : else if (!equiv_1 && equiv_2)
816 23447 : equiv_set = register_equiv (bb, v1, equiv_2);
817 4113849 : else if (equiv_1 && !equiv_2)
818 54015 : equiv_set = register_equiv (bb, v2, equiv_1);
819 : else
820 4059834 : 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 4147361 : if (!equiv_set)
825 : return false;
826 :
827 1867035 : add_equiv_to_block (bb, equiv_set);
828 1867035 : 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 9261138 : equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
836 : {
837 9261138 : 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 9261138 : limit_check (bb);
842 9261138 : if (!m_equiv[bb->index])
843 : {
844 5878633 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
845 : sizeof (equiv_chain));
846 5878633 : ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
847 5878633 : bitmap_copy (ptr->m_names, equiv_set);
848 5878633 : ptr->m_bb = bb;
849 5878633 : ptr->m_next = NULL;
850 5878633 : m_equiv[bb->index] = ptr;
851 : }
852 :
853 : // Now create the element for this equiv set and initialize it.
854 9261138 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
855 9261138 : ptr->m_names = equiv_set;
856 9261138 : ptr->m_bb = bb;
857 18522276 : gcc_checking_assert (bb->index < (int)m_equiv.length ());
858 9261138 : ptr->m_next = m_equiv[bb->index]->m_next;
859 9261138 : m_equiv[bb->index]->m_next = ptr;
860 9261138 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
861 : // Add BB to the equiv set.
862 9261138 : register_equiv_block (equiv_set, bb);
863 9261138 : }
864 :
865 : // Make sure the BB vector is big enough and grow it if needed.
866 :
867 : void
868 9261138 : equiv_oracle::limit_check (basic_block bb)
869 : {
870 9261138 : int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
871 18522276 : if (i >= (int)m_equiv.length ())
872 47 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
873 9261138 : }
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 2412129 : value_relation::intersect (value_relation &p)
945 : {
946 : // Save previous value
947 2412129 : relation_kind old = related;
948 :
949 2412129 : if (p.op1 () == op1 () && p.op2 () == op2 ())
950 2411808 : related = relation_intersect (kind (), p.kind ());
951 321 : else if (p.op2 () == op1 () && p.op1 () == op2 ())
952 321 : related = relation_intersect (kind (), relation_swap (p.kind ()));
953 : else
954 : return false;
955 :
956 2412129 : 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 13819149 : value_relation::apply_transitive (const value_relation &rel)
982 : {
983 13819149 : 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 13819149 : if (rel.op1 () == name2)
988 : {
989 : // A < B B < C
990 2179629 : if (rel.op2 () == name1)
991 : return false;
992 2111567 : k = relation_transitive (kind (), rel.kind ());
993 2111567 : if (k != VREL_VARYING)
994 : {
995 855477 : related = k;
996 855477 : name2 = rel.op2 ();
997 855477 : return true;
998 : }
999 : }
1000 11639520 : else if (rel.op1 () == name1)
1001 : {
1002 : // B > A B < C
1003 6632618 : if (rel.op2 () == name2)
1004 : return false;
1005 1813783 : k = relation_transitive (relation_swap (kind ()), rel.kind ());
1006 1813783 : if (k != VREL_VARYING)
1007 : {
1008 471758 : related = k;
1009 471758 : name1 = name2;
1010 471758 : name2 = rel.op2 ();
1011 471758 : return true;
1012 : }
1013 : }
1014 5006902 : else if (rel.op2 () == name2)
1015 : {
1016 : // A < B C > B
1017 4382663 : if (rel.op1 () == name1)
1018 : return false;
1019 4382663 : k = relation_transitive (kind (), relation_swap (rel.kind ()));
1020 4382663 : if (k != VREL_VARYING)
1021 : {
1022 531837 : related = k;
1023 531837 : name2 = rel.op1 ();
1024 531837 : return true;
1025 : }
1026 : }
1027 624239 : else if (rel.op2 () == name1)
1028 : {
1029 : // B > A C > B
1030 624239 : if (rel.op1 () == name2)
1031 : return false;
1032 624239 : k = relation_transitive (relation_swap (kind ()),
1033 : relation_swap (rel.kind ()));
1034 624239 : if (k != VREL_VARYING)
1035 : {
1036 238913 : related = k;
1037 238913 : name1 = name2;
1038 238913 : name2 = rel.op1 ();
1039 238913 : 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 53616560 : value_relation::create_trio (tree lhs, tree op1, tree op2)
1049 : {
1050 53616560 : relation_kind lhs_1;
1051 53616560 : if (lhs == name1 && op1 == name2)
1052 68927 : lhs_1 = related;
1053 53547633 : else if (lhs == name2 && op1 == name1)
1054 188212 : lhs_1 = relation_swap (related);
1055 : else
1056 : lhs_1 = VREL_VARYING;
1057 :
1058 53616560 : relation_kind lhs_2;
1059 53616560 : if (lhs == name1 && op2 == name2)
1060 54906 : lhs_2 = related;
1061 53561654 : else if (lhs == name2 && op2 == name1)
1062 133512 : lhs_2 = relation_swap (related);
1063 : else
1064 : lhs_2 = VREL_VARYING;
1065 :
1066 53616560 : relation_kind op_op;
1067 53616560 : if (op1 == name1 && op2 == name2)
1068 37763871 : op_op = related;
1069 15852689 : else if (op1 == name2 && op2 == name1)
1070 0 : op_op = relation_swap (related);
1071 15852689 : else if (op1 == op2)
1072 : op_op = VREL_EQ;
1073 : else
1074 15836955 : op_op = VREL_VARYING;
1075 :
1076 53616560 : return relation_trio (lhs_1, lhs_2, op_op);
1077 : }
1078 :
1079 : // Dump the relation to file F.
1080 :
1081 : void
1082 39792 : value_relation::dump (FILE *f) const
1083 : {
1084 39792 : if (!name1 || !name2)
1085 : {
1086 0 : fprintf (f, "no relation registered");
1087 0 : return;
1088 : }
1089 39792 : fputc ('(', f);
1090 39792 : print_generic_expr (f, op1 (), TDF_SLIM);
1091 39792 : print_relation (f, kind ());
1092 39792 : print_generic_expr (f, op2 (), TDF_SLIM);
1093 39792 : 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 84 : dom_oracle::next_relation (basic_block bb, relation_chain *ptr,
1111 : tree name) const
1112 : {
1113 84 : relation_chain *p;
1114 : // No value_relation pointer is used to initialize the iterator.
1115 84 : if (!ptr)
1116 : {
1117 37 : int bbi = bb->index;
1118 74 : if (bbi >= (int)m_relations.length())
1119 : return NULL;
1120 : else
1121 37 : p = m_relations[bbi].m_head;
1122 : }
1123 : else
1124 47 : p = ptr->m_next;
1125 :
1126 84 : 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 37 : block_relation_iterator::block_relation_iterator (const relation_oracle *oracle,
1138 : basic_block bb,
1139 : value_relation &vr,
1140 : tree name)
1141 : {
1142 37 : m_oracle = oracle;
1143 37 : m_bb = bb;
1144 37 : m_name = name;
1145 37 : m_ptr = oracle->next_relation (bb, NULL, m_name);
1146 37 : if (m_ptr)
1147 : {
1148 37 : m_done = false;
1149 37 : vr = *m_ptr;
1150 : }
1151 : else
1152 0 : m_done = true;
1153 37 : }
1154 :
1155 : // Retrieve the next relation from the iterator and return it in VR.
1156 :
1157 : void
1158 47 : block_relation_iterator::get_next_relation (value_relation &vr)
1159 : {
1160 47 : m_ptr = m_oracle->next_relation (m_bb, m_ptr, m_name);
1161 47 : if (m_ptr)
1162 : {
1163 10 : vr = *m_ptr;
1164 10 : 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 37 : m_done = true;
1175 47 : }
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 457836983 : relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
1184 : {
1185 457836983 : 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 219544455 : 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 13800966 : for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
1195 : {
1196 12117535 : unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1197 12117535 : unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1198 12117535 : if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
1199 2957351 : return ptr->kind ();
1200 9160184 : if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
1201 158289 : return relation_swap (ptr->kind ());
1202 : }
1203 :
1204 : return VREL_VARYING;
1205 : }
1206 :
1207 : // Instantiate a relation oracle.
1208 :
1209 27398343 : dom_oracle::dom_oracle (bool do_trans_p)
1210 : {
1211 27398343 : m_do_trans_p = do_trans_p;
1212 27398343 : m_relations.create (0);
1213 27398343 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1214 27398343 : m_relation_set = BITMAP_ALLOC (&m_bitmaps);
1215 27398343 : m_block_list.create (0);
1216 54796686 : m_block_list.safe_grow_cleared (num_ssa_names + 1);
1217 27398343 : m_tmp = BITMAP_ALLOC (&m_bitmaps);
1218 27398343 : m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
1219 27398343 : }
1220 :
1221 : // Destruct a relation oracle.
1222 :
1223 54796686 : dom_oracle::~dom_oracle ()
1224 : {
1225 27398343 : m_block_list.release ();
1226 27398343 : m_relations.release ();
1227 54796686 : }
1228 :
1229 : // Remove any relations with NAME from this list.
1230 :
1231 : void
1232 115 : relation_chain_head::clear (tree name)
1233 : {
1234 115 : unsigned v = SSA_NAME_VERSION (name);
1235 115 : if (!m_names || !bitmap_bit_p (m_names, v))
1236 : return;
1237 :
1238 115 : relation_chain *ptr, *last = NULL;;
1239 :
1240 185 : for (ptr = m_head; ptr; ptr = ptr->m_next)
1241 : {
1242 70 : tree op1 = ptr->op1 ();
1243 70 : tree op2 = ptr->op2 ();
1244 : // Delink any elements with NAME.
1245 70 : if (op1 == name || op2 == name)
1246 : {
1247 70 : if (!last)
1248 70 : m_head = ptr->m_next;
1249 : else
1250 0 : last->m_next = ptr->m_next;
1251 70 : m_num_relations--;
1252 : }
1253 : else
1254 : last = ptr;
1255 : }
1256 : // And remove name from the possible relations in this block bitfield.
1257 115 : bitmap_clear_bit (m_names, v);
1258 : }
1259 :
1260 : // Remove any relations involving NAME from the DOM oracle
1261 :
1262 : void
1263 440 : dom_oracle::clear (tree name)
1264 : {
1265 440 : equiv_oracle::clear (name);
1266 440 : unsigned v = SSA_NAME_VERSION (name);
1267 440 : if (bitmap_bit_p (m_relation_set, v))
1268 : {
1269 115 : gcc_checking_assert (m_block_list[v]);
1270 115 : bitmap_iterator bi;
1271 115 : unsigned bbi;
1272 :
1273 230 : EXECUTE_IF_SET_IN_BITMAP (m_block_list[v], 0, bbi, bi)
1274 : {
1275 115 : if (bbi >= m_relations.length())
1276 : break;
1277 115 : m_relations[bbi].clear (name);
1278 : }
1279 115 : bitmap_clear_bit (m_relation_set, v);
1280 115 : bitmap_clear (m_block_list[v]);
1281 : }
1282 440 : }
1283 :
1284 : // Register relation K between ssa_name OP1 and OP2 on STMT.
1285 : // Return false if no new relation is added.
1286 :
1287 : bool
1288 31049509 : relation_oracle::record (gimple *stmt, relation_kind k, tree op1, tree op2)
1289 : {
1290 31049509 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1291 31049509 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1292 31049509 : gcc_checking_assert (stmt && gimple_bb (stmt));
1293 :
1294 : // Don't register lack of a relation.
1295 31049509 : if (k == VREL_VARYING)
1296 : return false;
1297 :
1298 : // If an equivalence is being added between a PHI and one of its arguments
1299 : // make sure that that argument is not defined in the same block.
1300 : // This can happen along back edges and the equivalence will not be
1301 : // applicable as it would require a use before def.
1302 31049509 : if (k == VREL_EQ && is_a<gphi *> (stmt))
1303 : {
1304 1873455 : tree phi_def = gimple_phi_result (stmt);
1305 1873455 : gcc_checking_assert (phi_def == op1 || phi_def == op2);
1306 1873455 : tree arg = op2;
1307 1873455 : if (phi_def == op2)
1308 0 : arg = op1;
1309 1873455 : if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
1310 : return false;
1311 : }
1312 :
1313 : // If the LHS of a statement has already been processed and an equivalence
1314 : // registered, do not register another one. See PR 124809.
1315 74560701 : if (m_lhs_equiv_set_p && relation_equiv_p (k)
1316 44006034 : && gimple_get_lhs (stmt) == op1)
1317 : {
1318 12956525 : if (!bitmap_set_bit (m_lhs_equiv_set_p, SSA_NAME_VERSION (op1)))
1319 : return false;
1320 : }
1321 30554667 : bool ret = record (gimple_bb (stmt), k, op1, op2);
1322 :
1323 30554667 : if (ret && dump_file && (dump_flags & TDF_DETAILS))
1324 : {
1325 37838 : value_relation vr (k, op1, op2);
1326 37838 : fprintf (dump_file, " Registering value_relation ");
1327 37838 : vr.dump (dump_file);
1328 37838 : fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
1329 37838 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1330 : }
1331 : return ret;
1332 : }
1333 :
1334 : // Register relation K between ssa_name OP1 and OP2 on edge E.
1335 : // Return false if no new relation is added.
1336 :
1337 : bool
1338 6683461 : relation_oracle::record (edge e, relation_kind k, tree op1, tree op2)
1339 : {
1340 6683461 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1341 6683461 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1342 :
1343 : // Do not register lack of relation, or blocks which have more than
1344 : // edge E for a predecessor.
1345 6683461 : if (k == VREL_VARYING || !single_pred_p (e->dest))
1346 : return false;
1347 :
1348 6683461 : bool ret = record (e->dest, k, op1, op2);
1349 :
1350 6683461 : if (ret && dump_file && (dump_flags & TDF_DETAILS))
1351 : {
1352 120 : value_relation vr (k, op1, op2);
1353 120 : fprintf (dump_file, " Registering value_relation ");
1354 120 : vr.dump (dump_file);
1355 120 : fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
1356 : }
1357 : return ret;
1358 : }
1359 :
1360 : // Register relation K between OP! and OP2 in block BB.
1361 : // This creates the record and searches for existing records in the dominator
1362 : // tree to merge with. Return false if no new relation is added.
1363 :
1364 : bool
1365 36196746 : dom_oracle::record (basic_block bb, relation_kind k, tree op1, tree op2)
1366 : {
1367 : // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
1368 : // and no other relation makes sense.
1369 36196746 : if (op1 == op2)
1370 : return false;
1371 :
1372 : // Do not register an impossible relation.
1373 36185759 : if (k == VREL_UNDEFINED)
1374 : return false;
1375 :
1376 : // Equivalencies are handled by the equivalence oracle.
1377 36185759 : if (relation_equiv_p (k))
1378 14335530 : return equiv_oracle::record (bb, k, op1, op2);
1379 : else
1380 : {
1381 : // if neither op1 nor op2 are in a relation before this is registered,
1382 : // there will be no transitive.
1383 21850229 : bool check = bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op1))
1384 38258292 : || bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op2));
1385 21850229 : relation_chain *ptr = search_and_merge_relation (bb, k, op1, op2);
1386 21850229 : if (ptr && check
1387 21850229 : && (m_relations[bb->index].m_num_relations
1388 6374083 : < param_relation_block_limit))
1389 6373980 : register_transitives (bb, *ptr);
1390 : return ptr != NULL;
1391 : }
1392 : }
1393 :
1394 : void
1395 42961304 : dom_oracle::record_relation_block (unsigned v, unsigned bbi)
1396 : {
1397 42961304 : if (v>= m_block_list.length ())
1398 514 : m_block_list.safe_grow_cleared (num_ssa_names + 1);
1399 :
1400 42961304 : if (!m_block_list[v])
1401 30683962 : m_block_list[v] = BITMAP_ALLOC (&m_bitmaps);
1402 :
1403 42961304 : bitmap_set_bit (m_block_list[v], bbi);
1404 42961304 : }
1405 :
1406 : // Register relation K between OP1 and OP2 in block BB by creating a new
1407 : // record. It is an error for there to be an existing record.
1408 : // Return the record, or NULL if no record was created.
1409 :
1410 : relation_chain *
1411 21536083 : dom_oracle::create_relation_in_bb (basic_block bb, relation_kind k, tree op1,
1412 : tree op2)
1413 : {
1414 21536083 : int bbi = bb->index;
1415 :
1416 43072166 : if (bbi >= (int)m_relations.length())
1417 126 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1418 :
1419 21536083 : if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
1420 : return NULL;
1421 21480652 : m_relations[bbi].m_num_relations++;
1422 : // Check for an existing relation further up the DOM chain.
1423 : // By including dominating relations, The first one found in any search
1424 : // will be the aggregate of all the previous ones.
1425 :
1426 21480652 : relation_chain *ptr;
1427 :
1428 : // Summary bitmap indicating what ssa_names have relations in this BB.
1429 21480652 : bitmap bm = m_relations[bbi].m_names;
1430 21480652 : if (!bm)
1431 14465321 : bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
1432 21480652 : unsigned v1 = SSA_NAME_VERSION (op1);
1433 21480652 : unsigned v2 = SSA_NAME_VERSION (op2);
1434 :
1435 : // Assert there is no existing relation.
1436 21480652 : gcc_checking_assert (find_relation_block (bbi, op1, op2, NULL)
1437 : == VREL_VARYING);
1438 :
1439 21480652 : bitmap_set_bit (bm, v1);
1440 21480652 : bitmap_set_bit (bm, v2);
1441 21480652 : bitmap_set_bit (m_relation_set, v1);
1442 21480652 : bitmap_set_bit (m_relation_set, v2);
1443 21480652 : record_relation_block (v1, bbi);
1444 21480652 : record_relation_block (v2, bbi);
1445 :
1446 21480652 : ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1447 : sizeof (relation_chain));
1448 21480652 : ptr->set_relation (k, op1, op2);
1449 21480652 : ptr->m_next = m_relations[bbi].m_head;
1450 21480652 : m_relations[bbi].m_head = ptr;
1451 21480652 : return ptr;
1452 : }
1453 :
1454 : // Register relation K between OP1 and OP2 in block BB by searching the
1455 : // dominator tree for any existing record to merge with. If there were
1456 : // none, create a new record.
1457 : // Return the record, or NULL if no record was found or created.
1458 :
1459 : relation_chain *
1460 23948214 : dom_oracle::search_and_merge_relation (basic_block bb, relation_kind k,
1461 : tree op1, tree op2)
1462 : {
1463 : // Check for invalid relations to register.
1464 23948214 : gcc_checking_assert (k != VREL_VARYING && k != VREL_UNDEFINED
1465 : && k != VREL_EQ);
1466 :
1467 23948214 : relation_chain *ptr;
1468 23948214 : relation_kind curr = find_relation_block (bb->index, op1, op2, &ptr);
1469 :
1470 : // If there is an existing relation in this block, just intersect with it.
1471 23948214 : if (curr != VREL_VARYING)
1472 : {
1473 : // If K contradicts what is already recorded, the block is unreachable.
1474 : // Leave the existing relation alone rather than replacing it with
1475 : // UNDEFINED, matching what the dominator merge below does.
1476 2412131 : if (relation_intersect (curr, k) == VREL_UNDEFINED)
1477 : return NULL;
1478 : // If there was no change, return no record.
1479 2412129 : value_relation vr (k, op1, op2);
1480 2412129 : if (!ptr->intersect (vr))
1481 : return NULL;
1482 188631 : return ptr;
1483 : }
1484 :
1485 : // Create the relation in this block.
1486 21536083 : ptr = create_relation_in_bb (bb, k, op1, op2);
1487 21536083 : if (ptr)
1488 : {
1489 : // Check for an existing relation further up the DOM chain.
1490 : // By including dominating relations, The first one found in any search
1491 : // will be the aggregate of all the previous ones.
1492 21480652 : curr = find_relation_dom (get_immediate_dominator (CDI_DOMINATORS, bb),
1493 : op1, op2);
1494 21480652 : if (curr != VREL_VARYING)
1495 : {
1496 620365 : curr = relation_intersect (curr, k);
1497 : // Intersect the new relation with the existing one, unless the
1498 : // result is UNDEFINED. Then just leave it.
1499 620365 : if (curr != k && curr != VREL_UNDEFINED)
1500 170429 : ptr->set_relation (curr, op1, op2);
1501 : }
1502 : }
1503 21536083 : return ptr;
1504 : }
1505 :
1506 : // Starting at ROOT_BB search the DOM tree looking for relations which
1507 : // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
1508 : // bitmaps for op1/op2 and any of their equivalences that should also be
1509 : // considered.
1510 :
1511 : void
1512 6373980 : dom_oracle::register_transitives (basic_block root_bb,
1513 : const value_relation &relation)
1514 : {
1515 : // Only register transitives if they are requested.
1516 6373980 : if (!m_do_trans_p)
1517 : return;
1518 6373970 : basic_block bb;
1519 : // Only apply transitives to certain kinds of operations.
1520 6373970 : switch (relation.kind ())
1521 : {
1522 4658104 : case VREL_LE:
1523 4658104 : case VREL_LT:
1524 4658104 : case VREL_GT:
1525 4658104 : case VREL_GE:
1526 4658104 : break;
1527 : default:
1528 : return;
1529 : }
1530 :
1531 4658104 : const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb);
1532 4658104 : const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb);
1533 :
1534 4658104 : const unsigned work_budget = param_transitive_relations_work_bound;
1535 4658104 : unsigned avail_budget = work_budget;
1536 91086207 : for (bb = root_bb; bb;
1537 : /* Advancing to the next immediate dominator eats from the budget,
1538 : if none is left after that there's no point to continue. */
1539 : bb = (--avail_budget > 0
1540 86488330 : ? get_immediate_dominator (CDI_DOMINATORS, bb) : nullptr))
1541 : {
1542 86565264 : int bbi = bb->index;
1543 173130528 : if (bbi >= (int)m_relations.length())
1544 4639 : continue;
1545 86560625 : const_bitmap bm = m_relations[bbi].m_names;
1546 86560625 : if (!bm)
1547 62051115 : continue;
1548 24509510 : if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
1549 16093478 : continue;
1550 : // At least one of the 2 ops has a relation in this block.
1551 8416032 : relation_chain *ptr;
1552 37086832 : for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
1553 : {
1554 : // In the presence of an equivalence, 2 operands may do not
1555 : // naturally match. ie with equivalence a_2 == b_3
1556 : // given c_1 < a_2 && b_3 < d_4
1557 : // convert the second relation (b_3 < d_4) to match any
1558 : // equivalences to found in the first relation.
1559 : // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1560 : // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1561 :
1562 28747734 : tree r1, r2;
1563 28747734 : tree p1 = ptr->op1 ();
1564 28747734 : tree p2 = ptr->op2 ();
1565 : // Find which equivalence is in the first operand.
1566 28747734 : if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
1567 : r1 = p1;
1568 22115082 : else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
1569 : r1 = p2;
1570 : else
1571 21422781 : r1 = NULL_TREE;
1572 :
1573 : // Find which equivalence is in the second operand.
1574 28747734 : if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
1575 : r2 = p1;
1576 26568071 : else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
1577 : r2 = p2;
1578 : else
1579 17366573 : r2 = NULL_TREE;
1580 :
1581 : // Ignore if both NULL (not relevant relation) or the same,
1582 28747734 : if (r1 == r2)
1583 : ;
1584 :
1585 : else
1586 : {
1587 : // Any operand not an equivalence, just take the real operand.
1588 13819149 : if (!r1)
1589 6494230 : r1 = relation.op1 ();
1590 13819149 : if (!r2)
1591 2438022 : r2 = relation.op2 ();
1592 :
1593 13819149 : value_relation nr (relation.kind (), r1, r2);
1594 13819149 : if (nr.apply_transitive (*ptr))
1595 : {
1596 : // If the new relation is already present we know any
1597 : // further processing is already reflected above it.
1598 : // When we ran into the limit of relations on root_bb
1599 : // we can give up as well.
1600 2097985 : if (!search_and_merge_relation (root_bb, nr.kind (),
1601 : nr.op1 (), nr.op2 ()))
1602 70043 : return;
1603 2027942 : if (dump_file && (dump_flags & TDF_DETAILS))
1604 : {
1605 1448 : fprintf (dump_file,
1606 : " Registering transitive relation ");
1607 1448 : nr.dump (dump_file);
1608 1448 : fputc ('\n', dump_file);
1609 : }
1610 : }
1611 : }
1612 : /* Processed one relation, abort if we've eaten up our budget. */
1613 28677691 : if (--avail_budget == 0)
1614 : return;
1615 : }
1616 : }
1617 : }
1618 :
1619 : // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1620 : // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1621 :
1622 : relation_kind
1623 406688142 : dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
1624 : const_bitmap b2) const
1625 : {
1626 406688142 : if (bb >= m_relations.length())
1627 : return VREL_VARYING;
1628 :
1629 406686531 : return m_relations[bb].find_relation (b1, b2);
1630 : }
1631 :
1632 : // Search the DOM tree for a relation between an element of equivalency set B1
1633 : // and B2, starting with block BB.
1634 :
1635 : relation_kind
1636 26034405 : dom_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
1637 : {
1638 26034405 : relation_kind r;
1639 26034405 : if (bitmap_equal_p (b1, b2))
1640 : return VREL_EQ;
1641 :
1642 : // If either name does not occur in a relation anywhere, there isn't one.
1643 26034405 : if (!bitmap_intersect_p (m_relation_set, b1)
1644 26034405 : || !bitmap_intersect_p (m_relation_set, b2))
1645 : return VREL_VARYING;
1646 :
1647 : // Search each block in the DOM tree checking.
1648 421407331 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1649 : {
1650 406688142 : r = find_relation_block (bb->index, b1, b2);
1651 406688142 : if (r != VREL_VARYING)
1652 : return r;
1653 : }
1654 : return VREL_VARYING;
1655 :
1656 : }
1657 :
1658 : // Find a relation in block BB between ssa version V1 and V2. If a relation
1659 : // is found, return a pointer to the chain object in OBJ.
1660 :
1661 : relation_kind
1662 1142370677 : dom_oracle::find_relation_block (int bb, tree ssa1, tree ssa2,
1663 : relation_chain **obj) const
1664 : {
1665 2284741354 : if (bb >= (int)m_relations.length())
1666 : return VREL_VARYING;
1667 :
1668 1142353341 : const_bitmap bm = m_relations[bb].m_names;
1669 1142353341 : if (!bm)
1670 : return VREL_VARYING;
1671 :
1672 514073872 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1673 514073872 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1674 :
1675 : // If both b1 and b2 aren't referenced in this block, cant be a relation
1676 514073872 : if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1677 : return VREL_VARYING;
1678 :
1679 12552353 : relation_chain *ptr;
1680 70967562 : for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1681 : {
1682 67970011 : tree op1 = ptr->op1 ();
1683 67970011 : tree op2 = ptr->op2 ();
1684 67970011 : if (ssa1 == op1 && ssa2 == op2)
1685 : {
1686 9254322 : if (obj)
1687 2411810 : *obj = ptr;
1688 9254322 : return ptr->kind ();
1689 : }
1690 58715689 : if (ssa1 == op2 && ssa2 == op1)
1691 : {
1692 300480 : if (obj)
1693 321 : *obj = ptr;
1694 300480 : return relation_swap (ptr->kind ());
1695 : }
1696 : }
1697 :
1698 : return VREL_VARYING;
1699 : }
1700 :
1701 : // See if a relation can be found between SSA1 and SSA2 in basic block BB based
1702 : // on values as they exist in basic block ORIG. This will only occur
1703 : // if SSA1 and SSA2 occur in the same statement together.
1704 :
1705 : relation_kind
1706 737120173 : dom_oracle::recomputed_relation (basic_block orig_bb, edge e, tree ssa1,
1707 : tree ssa2) const
1708 : {
1709 737120173 : if (ssa1 == ssa2)
1710 : return VREL_EQ;
1711 1474240346 : gori_map *gori_ssa = get_range_query (cfun)->gori_ssa ();
1712 737120173 : if (!gori_ssa)
1713 : return VREL_VARYING;
1714 :
1715 : // If SSA1 and SSA2 are not BOTH exported from the block, theres no relation.
1716 666819657 : basic_block bb = e->src;
1717 666819657 : if (!gori_ssa->is_export_p (ssa1, bb) || !gori_ssa->is_export_p (ssa2, bb))
1718 : return VREL_VARYING;
1719 :
1720 : // Verify the edge is a range generating edge.
1721 656356 : gimple_outgoing_range &gori = get_range_query (cfun)->gori ();
1722 328178 : int_range_max edge_range;
1723 328178 : gimple *stmt = gori.edge_range_p (edge_range, e);
1724 328178 : if (!stmt)
1725 : return VREL_VARYING;
1726 :
1727 : // Scan back thru the dependency chain recalculating values as if they are
1728 : // in ORIG_BB, and see if we can find a statement with both op1 and op2
1729 : // which generates a relation.
1730 :
1731 328178 : value_range lhs_range (edge_range);
1732 :
1733 328178 : while (stmt)
1734 : {
1735 522726 : bool ret;
1736 522726 : gimple_range_op_handler handler (stmt);
1737 522726 : if (!handler)
1738 328178 : return VREL_VARYING;
1739 :
1740 522708 : tree op1 = handler.operand1 ();
1741 522708 : tree op2 = handler.operand2 ();
1742 522708 : value_range op1_range (TREE_TYPE (op1));
1743 522708 : value_range op2_range;
1744 :
1745 : // Check if this is the statment we are looking for!
1746 522708 : bool match = (op1 == ssa1 && op2 == ssa2);
1747 522708 : bool match_rev = (op2 == ssa1 && op1 == ssa2);
1748 522708 : if (match || match_rev)
1749 : {
1750 87215 : gcc_checking_assert (op2);
1751 87215 : op2_range.set_range_class (TREE_TYPE (op2));
1752 : // Pick up the ranges at ORIG_BB, and see if a relation is generated.
1753 174430 : get_range_query (cfun)->range_on_entry (op1_range, orig_bb, op1);
1754 174430 : get_range_query (cfun)->range_on_entry (op2_range, orig_bb, op2);
1755 87215 : relation_kind relation = handler.op1_op2_relation (lhs_range,
1756 87215 : op1_range,
1757 87215 : op2_range);
1758 : // If the operands are reversed, swap the relation.
1759 87215 : if (match_rev)
1760 21492 : relation = relation_swap (relation);
1761 : return relation;
1762 : }
1763 :
1764 : // Now determine if one of the operands has both SSA1 and SSA2 in
1765 : // the dependency chain. Thats the path we want to follow.
1766 435493 : bool op1_dep = gimple_range_ssa_p (op1)
1767 432327 : && gori_ssa->in_chain_p (ssa1, op1)
1768 688872 : && gori_ssa->in_chain_p (ssa2, op1);
1769 435493 : bool op2_dep = gimple_range_ssa_p (op2)
1770 266954 : && gori_ssa->in_chain_p (ssa1, op2)
1771 544874 : && gori_ssa->in_chain_p (ssa2, op2);
1772 : // If there are no dependencies with both names, or both sides have
1773 : // both names, simply bail.
1774 435493 : if (op1_dep == op2_dep)
1775 : return VREL_VARYING;
1776 :
1777 252548 : if (op1_dep)
1778 : {
1779 : // If operand 1 is the chain we are interested in, calcualte its
1780 : // range based on LHS_RANGE.
1781 190623 : if (!op2)
1782 17903 : ret = handler.calc_op1 (op1_range, lhs_range);
1783 : else
1784 : {
1785 : // Pick up the range of op2 as it occurs in the original block.
1786 : // and calculate a range for op1.
1787 172720 : op2_range.set_range_class (TREE_TYPE (op2));
1788 345440 : get_range_query (cfun)->range_on_entry (op2_range, orig_bb, op2);
1789 172720 : ret = handler.calc_op1 (op1_range, lhs_range, op2_range);
1790 : }
1791 : // If we failed to calculate a range for op1, bail.
1792 190623 : if (!ret)
1793 : return VREL_VARYING;
1794 :
1795 : // op1_range will now become the LHS_RANGE for the def statement.
1796 186121 : lhs_range = op1_range;
1797 186121 : stmt = SSA_NAME_DEF_STMT (op1);
1798 : }
1799 61925 : else if (op2_dep)
1800 : {
1801 : // Pick up the range of op1 as it occurs in the original block.
1802 : // and calcalute a range for op2.
1803 61925 : op2_range.set_range_class (TREE_TYPE (op2));
1804 123850 : get_range_query (cfun)->range_on_entry (op1_range, orig_bb, op1);
1805 61925 : ret = handler.calc_op2 (op2_range, lhs_range, op1_range);
1806 : // If we failed to calculate a range for op1, bail.
1807 61925 : if (!ret)
1808 : return VREL_VARYING;
1809 :
1810 : // op2_range will now become the LHS_RANGE for the def statement.
1811 61443 : lhs_range = op2_range;
1812 61443 : stmt = SSA_NAME_DEF_STMT (op2);
1813 : }
1814 : else
1815 0 : gcc_unreachable ();
1816 :
1817 : // Bail if this ssa-name is defined outside this block.
1818 247564 : if (!stmt || gimple_bb (stmt) != e->src)
1819 : return VREL_VARYING;
1820 522708 : }
1821 : return VREL_VARYING;
1822 328178 : }
1823 :
1824 : // Find a relation between SSA version V1 and V2 in the dominator tree
1825 : // starting with block BB
1826 :
1827 : relation_kind
1828 42641370 : dom_oracle::find_relation_dom (basic_block start_bb, tree ssa1, tree ssa2) const
1829 : {
1830 42641370 : relation_kind r;
1831 42641370 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1832 42641370 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1833 : // IF either name does not occur in a relation anywhere, there isn't one.
1834 42641370 : if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1835 : return VREL_VARYING;
1836 : edge outgoing_edge = NULL;
1837 1089792356 : for (basic_block bb = start_bb;
1838 1130768202 : bb;
1839 1089792356 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1840 : {
1841 1096941811 : r = find_relation_block (bb->index, ssa1, ssa2);
1842 : // Now check if recomputed values on the outgoing edge might create
1843 : // a relation.
1844 1096941811 : if (r == VREL_VARYING && outgoing_edge)
1845 : {
1846 737120173 : gcc_checking_assert (outgoing_edge->src == bb);
1847 737120173 : r = recomputed_relation (start_bb, outgoing_edge, ssa1, ssa2);
1848 : }
1849 1096941811 : if (r != VREL_VARYING)
1850 : return r;
1851 :
1852 : // If the dominator is not the only predecessor to this block, there is
1853 : // unlikely to be a viable relation available.
1854 1089792356 : outgoing_edge = single_pred_p (bb) ? single_pred_edge (bb) : NULL;
1855 : }
1856 : return VREL_VARYING;
1857 : }
1858 :
1859 : // Query if there is a relation between SSA1 and SS2 in block BB or a
1860 : // dominator of BB
1861 :
1862 : relation_kind
1863 99489610 : dom_oracle::query (basic_block bb, tree ssa1, tree ssa2)
1864 : {
1865 99489610 : relation_kind kind;
1866 99489610 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1867 99489610 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1868 99489610 : if (v1 == v2)
1869 : return VREL_EQ;
1870 :
1871 : // If v1 or v2 do not have any relations or equivalences, a partial
1872 : // equivalence is the only possibility.
1873 167580941 : if ((!bitmap_bit_p (m_relation_set, v1) && !has_equiv_p (v1))
1874 102546226 : || (!bitmap_bit_p (m_relation_set, v2) && !has_equiv_p (v2)))
1875 78109629 : return partial_equiv (ssa1, ssa2);
1876 :
1877 : // Check for equivalence first. They must be in each equivalency set.
1878 21278191 : const_bitmap equiv1 = equiv_set (ssa1, bb);
1879 21278191 : const_bitmap equiv2 = equiv_set (ssa2, bb);
1880 21278191 : if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
1881 : return VREL_EQ;
1882 :
1883 : // A statement such as c = a & 0xff makes a partial equivalence between
1884 : // c and a, and an ordinary comparison can then relate the same pair.
1885 : // If both exist, prefer the relation, so look for that first.
1886 21160718 : kind = find_relation_dom (bb, ssa1, ssa2);
1887 : // If no direct relation exists, try the query using the equivalence sets.
1888 21160718 : if (kind == VREL_VARYING)
1889 14631628 : kind = query (bb, equiv1, equiv2);
1890 :
1891 : // Finally look for partial equivalences.
1892 14631628 : if (kind == VREL_VARYING)
1893 14546909 : kind = partial_equiv (ssa1, ssa2);
1894 : return kind;
1895 : }
1896 :
1897 : // Dump all the relations in block BB to file F.
1898 :
1899 : void
1900 257 : dom_oracle::dump (FILE *f, basic_block bb) const
1901 : {
1902 257 : equiv_oracle::dump (f,bb);
1903 :
1904 514 : if (bb->index >= (int)m_relations.length ())
1905 220 : return;
1906 257 : if (!m_relations[bb->index].m_names)
1907 : return;
1908 :
1909 37 : value_relation vr;
1910 84 : FOR_EACH_RELATION_BB (this, bb, vr)
1911 : {
1912 47 : fprintf (f, "Relational : ");
1913 47 : vr.dump (f);
1914 47 : fprintf (f, "\n");
1915 : }
1916 : }
1917 :
1918 : // Dump all the relations known to file F.
1919 :
1920 : void
1921 0 : dom_oracle::dump (FILE *f) const
1922 : {
1923 0 : fprintf (f, "Relation dump\n");
1924 0 : for (unsigned i = 0; i < m_relations.length (); i++)
1925 0 : if (BASIC_BLOCK_FOR_FN (cfun, i))
1926 : {
1927 0 : fprintf (f, "BB%d\n", i);
1928 0 : dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
1929 : }
1930 0 : }
1931 :
1932 : void
1933 0 : relation_oracle::debug () const
1934 : {
1935 0 : dump (stderr);
1936 0 : }
1937 :
1938 9411288 : path_oracle::path_oracle (relation_oracle *oracle)
1939 : {
1940 9411288 : set_root_oracle (oracle);
1941 9411288 : bitmap_obstack_initialize (&m_bitmaps);
1942 9411288 : obstack_init (&m_chain_obstack);
1943 :
1944 : // Initialize header records.
1945 9411288 : m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
1946 9411288 : m_equiv.m_bb = NULL;
1947 9411288 : m_equiv.m_next = NULL;
1948 9411288 : m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
1949 9411288 : m_relations.m_head = NULL;
1950 9411288 : m_killed_defs = BITMAP_ALLOC (&m_bitmaps);
1951 9411288 : }
1952 :
1953 18822576 : path_oracle::~path_oracle ()
1954 : {
1955 9411288 : obstack_free (&m_chain_obstack, NULL);
1956 9411288 : bitmap_obstack_release (&m_bitmaps);
1957 18822576 : }
1958 :
1959 : // Clear any range info and relations associated with NAME.
1960 :
1961 : void
1962 0 : path_oracle::clear (tree name)
1963 : {
1964 0 : if (m_root)
1965 0 : m_root->clear (name);
1966 :
1967 0 : m_relations.clear (name);
1968 :
1969 0 : unsigned v = SSA_NAME_VERSION (name);
1970 0 : equiv_chain *ptr = m_equiv.find (v);
1971 0 : if (ptr)
1972 0 : bitmap_clear_bit (ptr->m_names, v);
1973 0 : }
1974 :
1975 : // Return the equiv set for SSA, and if there isn't one, check for equivs
1976 : // starting in block BB.
1977 :
1978 : const_bitmap
1979 139759695 : path_oracle::equiv_set (tree ssa, basic_block bb)
1980 : {
1981 : // Check the list first.
1982 139759695 : equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
1983 139759695 : if (ptr)
1984 75616854 : return ptr->m_names;
1985 :
1986 : // Otherwise defer to the root oracle.
1987 64142841 : if (m_root)
1988 57928782 : return m_root->equiv_set (ssa, bb);
1989 :
1990 : // Allocate a throw away bitmap if there isn't a root oracle.
1991 6214059 : bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
1992 6214059 : bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
1993 6214059 : return tmp;
1994 : }
1995 :
1996 : // Register an equivalence between SSA1 and SSA2 resolving unknowns from
1997 : // block BB. Return false if no new equivalence was added.
1998 :
1999 : bool
2000 8793500 : path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
2001 : {
2002 8793500 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
2003 8793500 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
2004 :
2005 : // Check if they are the same set, if so, we're done.
2006 8793500 : if (bitmap_equal_p (equiv_1, equiv_2))
2007 : return false;
2008 :
2009 : // Don't mess around, simply create a new record and insert it first.
2010 8778773 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
2011 8778773 : valid_equivs (b, equiv_1, bb);
2012 8778773 : valid_equivs (b, equiv_2, bb);
2013 :
2014 8778773 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
2015 : sizeof (equiv_chain));
2016 8778773 : ptr->m_names = b;
2017 8778773 : ptr->m_bb = NULL;
2018 8778773 : ptr->m_next = m_equiv.m_next;
2019 8778773 : m_equiv.m_next = ptr;
2020 8778773 : bitmap_ior_into (m_equiv.m_names, b);
2021 8778773 : return true;
2022 : }
2023 :
2024 : // Register killing definition of an SSA_NAME.
2025 :
2026 : void
2027 60873454 : path_oracle::killing_def (tree ssa)
2028 : {
2029 60873454 : if (dump_file && (dump_flags & TDF_DETAILS))
2030 : {
2031 828 : fprintf (dump_file, " Registering killing_def (path_oracle) ");
2032 828 : print_generic_expr (dump_file, ssa, TDF_SLIM);
2033 828 : fprintf (dump_file, "\n");
2034 : }
2035 :
2036 60873454 : unsigned v = SSA_NAME_VERSION (ssa);
2037 :
2038 60873454 : bitmap_set_bit (m_killed_defs, v);
2039 60873454 : bitmap_set_bit (m_equiv.m_names, v);
2040 :
2041 : // Now add an equivalency with itself so we don't look to the root oracle.
2042 60873454 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
2043 60873454 : bitmap_set_bit (b, v);
2044 60873454 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
2045 : sizeof (equiv_chain));
2046 60873454 : ptr->m_names = b;
2047 60873454 : ptr->m_bb = NULL;
2048 60873454 : ptr->m_next = m_equiv.m_next;
2049 60873454 : m_equiv.m_next = ptr;
2050 :
2051 : // Walk the relation list and remove SSA from any relations.
2052 60873454 : if (!bitmap_bit_p (m_relations.m_names, v))
2053 : return;
2054 :
2055 64568 : bitmap_clear_bit (m_relations.m_names, v);
2056 64568 : relation_chain **prev = &(m_relations.m_head);
2057 64568 : relation_chain *next = NULL;
2058 186133 : for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
2059 : {
2060 121565 : gcc_checking_assert (*prev == ptr);
2061 121565 : next = ptr->m_next;
2062 121565 : if (SSA_NAME_VERSION (ptr->op1 ()) == v
2063 121565 : || SSA_NAME_VERSION (ptr->op2 ()) == v)
2064 63498 : *prev = ptr->m_next;
2065 : else
2066 58067 : prev = &(ptr->m_next);
2067 : }
2068 : }
2069 :
2070 : // Register relation K between SSA1 and SSA2, resolving unknowns by
2071 : // querying from BB. Return false if no new relation is registered.
2072 :
2073 : bool
2074 30843700 : path_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
2075 : {
2076 : // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
2077 : // and no other relation makes sense.
2078 30843700 : if (ssa1 == ssa2)
2079 : return false;
2080 :
2081 : // Partial equivalences are tracked in the root equivalence oracle rather
2082 : // than on the path. Registering a partial equivalence in the path would
2083 : // cause normal relations to collapse to VARYING.
2084 30798617 : if (relation_partial_equiv_p (k))
2085 : return false;
2086 :
2087 27255458 : relation_kind curr = query (bb, ssa1, ssa2);
2088 : // Likewise, a partial equivalency result should not be combined with K
2089 : // or the result drops to VARYING.
2090 27255458 : if (curr != VREL_VARYING && !relation_partial_equiv_p (curr))
2091 3879255 : k = relation_intersect (curr, k);
2092 :
2093 : // Do not register an impossible relation.
2094 27255458 : if (k == VREL_UNDEFINED)
2095 : return false;
2096 :
2097 24985673 : bool ret;
2098 24985673 : if (k == VREL_EQ)
2099 8793500 : ret = register_equiv (bb, ssa1, ssa2);
2100 : else
2101 : {
2102 16192173 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
2103 16192173 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
2104 16192173 : relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
2105 : sizeof (relation_chain));
2106 16192173 : ptr->set_relation (k, ssa1, ssa2);
2107 16192173 : ptr->m_next = m_relations.m_head;
2108 16192173 : m_relations.m_head = ptr;
2109 16192173 : ret = true;
2110 : }
2111 :
2112 24985673 : if (ret && dump_file && (dump_flags & TDF_DETAILS))
2113 : {
2114 297 : value_relation vr (k, ssa1, ssa2);
2115 297 : fprintf (dump_file, " Registering value_relation (path_oracle) ");
2116 297 : vr.dump (dump_file);
2117 297 : fprintf (dump_file, " (root: bb%d)\n", bb->index);
2118 : }
2119 : return ret;
2120 : }
2121 :
2122 : // Query for a relationship between equiv set B1 and B2, resolving unknowns
2123 : // starting at block BB.
2124 :
2125 : relation_kind
2126 51150452 : path_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
2127 : {
2128 51150452 : if (bitmap_equal_p (b1, b2))
2129 : return VREL_EQ;
2130 :
2131 51150452 : relation_kind k = m_relations.find_relation (b1, b2);
2132 :
2133 : // Do not look at the root oracle for names that have been killed
2134 : // along the path.
2135 51150452 : if (bitmap_intersect_p (m_killed_defs, b1)
2136 51150452 : || bitmap_intersect_p (m_killed_defs, b2))
2137 : return k;
2138 :
2139 : // Query the root oracle for relations with path local equivalencies.
2140 13695896 : if (k == VREL_VARYING && m_root)
2141 11402777 : k = m_root->query (bb, b1, b2);
2142 :
2143 : return k;
2144 : }
2145 :
2146 : // Query for a relationship between SSA1 and SSA2, resolving unknowns
2147 : // starting at block BB.
2148 :
2149 : relation_kind
2150 51839062 : path_oracle::query (basic_block bb, tree ssa1, tree ssa2)
2151 : {
2152 51839062 : unsigned v1 = SSA_NAME_VERSION (ssa1);
2153 51839062 : unsigned v2 = SSA_NAME_VERSION (ssa2);
2154 :
2155 51839062 : if (v1 == v2)
2156 : return VREL_EQ;
2157 :
2158 51745521 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
2159 51745521 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
2160 51745521 : if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
2161 : return VREL_EQ;
2162 :
2163 51150452 : relation_kind rel = query (bb, equiv_1, equiv_2);
2164 :
2165 : // If the path relation query fails, check for relations in the root oracle.
2166 51150452 : if (rel == VREL_VARYING && m_root)
2167 44580982 : rel = m_root->query (bb, ssa1, ssa2);
2168 : return rel;
2169 : }
2170 :
2171 : // Reset any relations registered on this path. ORACLE is the root
2172 : // oracle to use.
2173 :
2174 : void
2175 40343465 : path_oracle::reset_path (relation_oracle *oracle)
2176 : {
2177 40343465 : set_root_oracle (oracle);
2178 40343465 : m_equiv.m_next = NULL;
2179 40343465 : bitmap_clear (m_equiv.m_names);
2180 40343465 : m_relations.m_head = NULL;
2181 40343465 : bitmap_clear (m_relations.m_names);
2182 40343465 : bitmap_clear (m_killed_defs);
2183 40343465 : }
2184 :
2185 : // Dump relation in basic block... Do nothing here.
2186 :
2187 : void
2188 0 : path_oracle::dump (FILE *, basic_block) const
2189 : {
2190 0 : }
2191 :
2192 : // Dump the relations and equivalencies found in the path.
2193 :
2194 : void
2195 0 : path_oracle::dump (FILE *f) const
2196 : {
2197 0 : equiv_chain *ptr = m_equiv.m_next;
2198 0 : relation_chain *ptr2 = m_relations.m_head;
2199 :
2200 0 : if (ptr || ptr2)
2201 0 : fprintf (f, "\npath_oracle:\n");
2202 :
2203 0 : for (; ptr; ptr = ptr->m_next)
2204 0 : ptr->dump (f);
2205 :
2206 0 : for (; ptr2; ptr2 = ptr2->m_next)
2207 : {
2208 0 : fprintf (f, "Relational : ");
2209 0 : ptr2->dump (f);
2210 0 : fprintf (f, "\n");
2211 : }
2212 0 : }
2213 :
2214 : // ------------------------------------------------------------------------
2215 : // EQUIV iterator. Although we have bitmap iterators, don't expose that it
2216 : // is currently a bitmap. Use an export iterator to hide future changes.
2217 :
2218 : // Construct a basic iterator over an equivalence bitmap.
2219 :
2220 52829638 : equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle,
2221 : basic_block bb, tree name,
2222 : bool full, bool partial)
2223 : {
2224 52829638 : m_name = name;
2225 52829638 : m_oracle = oracle;
2226 52829638 : m_pe = partial ? oracle->partial_equiv_set (name) : NULL;
2227 52829638 : m_bm = NULL;
2228 52829638 : if (full)
2229 52829638 : m_bm = oracle->equiv_set (name, bb);
2230 52829638 : if (!m_bm && m_pe)
2231 0 : m_bm = m_pe->members;
2232 52829638 : if (m_bm)
2233 52829637 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
2234 52829638 : }
2235 :
2236 : // Move to the next export bitmap spot.
2237 :
2238 : void
2239 68782210 : equiv_relation_iterator::next ()
2240 : {
2241 68782210 : bmp_iter_next (&m_bi, &m_y);
2242 68782210 : }
2243 :
2244 : // Fetch the name of the next export in the export list. Return NULL if
2245 : // iteration is done.
2246 :
2247 : tree
2248 62804129 : equiv_relation_iterator::get_name (relation_kind *rel)
2249 : {
2250 68782053 : if (!m_bm)
2251 : return NULL_TREE;
2252 :
2253 127589771 : while (bmp_iter_set (&m_bi, &m_y))
2254 : {
2255 : // Do not return self.
2256 68782210 : tree t = ssa_name (m_y);
2257 68782210 : if (t && t != m_name)
2258 : {
2259 9974507 : relation_kind k = VREL_EQ;
2260 9974507 : if (m_pe && m_bm == m_pe->members)
2261 : {
2262 7666779 : const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t);
2263 7666779 : if (equiv_pe && equiv_pe->members == m_pe->members)
2264 7666763 : k = pe_min (m_pe->code, equiv_pe->code);
2265 : else
2266 : k = VREL_VARYING;
2267 : }
2268 7666779 : if (relation_equiv_p (k))
2269 : {
2270 9974491 : if (rel)
2271 9974491 : *rel = k;
2272 : return t;
2273 : }
2274 : }
2275 58807719 : next ();
2276 : }
2277 :
2278 : // Process partial equivs after full equivs if both were requested.
2279 58807561 : if (m_pe && m_bm != m_pe->members)
2280 : {
2281 52829637 : m_bm = m_pe->members;
2282 52829637 : if (m_bm)
2283 : {
2284 : // Recursively call back to process First PE.
2285 5977924 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
2286 5977924 : return get_name (rel);
2287 : }
2288 : }
2289 : return NULL_TREE;
2290 : }
2291 :
2292 : #if CHECKING_P
2293 : #include "selftest.h"
2294 :
2295 : namespace selftest
2296 : {
2297 : void
2298 4 : relation_tests ()
2299 : {
2300 : // rr_*_table tables use unsigned char rather than relation_kind.
2301 4 : ASSERT_LT (VREL_LAST, UCHAR_MAX);
2302 52 : for (relation_kind r1 = VREL_VARYING; r1 < VREL_LAST;
2303 48 : r1 = relation_kind (r1 + 1))
2304 : {
2305 : // Swapping the operands twice is a no-op.
2306 48 : ASSERT_EQ (relation_swap (relation_swap (r1)), r1);
2307 :
2308 : // VARYING intersect X is X.
2309 : // UNDEFINED intersect X is UNDEFINED.
2310 48 : ASSERT_EQ (relation_intersect (VREL_VARYING, r1), r1);
2311 48 : ASSERT_EQ (relation_intersect (VREL_UNDEFINED, r1), VREL_UNDEFINED);
2312 :
2313 : // UNDEFINED union X is X.
2314 : // VARYING union X is VARYING.
2315 48 : ASSERT_EQ (relation_union (VREL_UNDEFINED, r1), r1);
2316 48 : ASSERT_EQ (relation_union (VREL_VARYING, r1), VREL_VARYING);
2317 :
2318 : // Verify commutativity of relation_intersect and relation_union.
2319 624 : for (relation_kind r2 = VREL_VARYING; r2 < VREL_LAST;
2320 576 : r2 = relation_kind (r2 + 1))
2321 : {
2322 576 : ASSERT_EQ (relation_intersect (r1, r2), relation_intersect (r2, r1));
2323 576 : ASSERT_EQ (relation_union (r1, r2), relation_union (r2, r1));
2324 : }
2325 : }
2326 :
2327 : // Verify partial equivalence properties.
2328 20 : for (relation_kind r1 = VREL_PE8; r1 <= VREL_PE64;
2329 16 : r1 = relation_kind (r1 + 1))
2330 : {
2331 16 : ASSERT_EQ (relation_swap (r1), r1);
2332 16 : ASSERT_EQ (relation_intersect (VREL_EQ, r1), VREL_EQ);
2333 16 : ASSERT_EQ (relation_union (VREL_EQ, r1), r1);
2334 16 : ASSERT_EQ (relation_transitive (VREL_EQ, r1), r1);
2335 16 : ASSERT_EQ (relation_transitive (r1, VREL_EQ), r1);
2336 80 : for (relation_kind r2 = VREL_PE8; r2 <= VREL_PE64;
2337 64 : r2 = relation_kind (r2 + 1))
2338 : {
2339 64 : ASSERT_EQ (relation_intersect (r1, r2), MAX (r1, r2));
2340 64 : ASSERT_EQ (relation_union (r1, r2), pe_min (r1, r2));
2341 64 : ASSERT_EQ (relation_transitive (r1, r2), pe_min (r1, r2));
2342 : }
2343 : }
2344 4 : }
2345 :
2346 : } // namespace selftest
2347 :
2348 : #endif // CHECKING_P
|
