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 39911 : print_relation (FILE *f, relation_kind rel)
43 : {
44 39911 : fprintf (f, " %s ", kind_string[rel]);
45 39911 : }
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 58055072 : relation_swap (relation_kind r)
71 : {
72 58055072 : 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 127416510 : relation_intersect (relation_kind r1, relation_kind r2)
134 : {
135 127416510 : 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 91528087 : relation_union (relation_kind r1, relation_kind r2)
193 : {
194 91528087 : 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 54344758 : relation_transitive (relation_kind r1, relation_kind r2)
257 : {
258 54344758 : 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 2512309 : adjust_equivalence_range (vrange &range)
267 : {
268 2512309 : if (range.undefined_p () || !is_a<frange> (range))
269 2474664 : return;
270 :
271 37645 : frange fr = as_a<frange> (range);
272 : // If range includes 0 make sure both signs of zero are included.
273 37645 : if (fr.contains_p (dconst0) || fr.contains_p (dconstm0))
274 : {
275 19296 : frange zeros (range.type (), dconstm0, dconst0);
276 19296 : range.union_ (zeros);
277 19296 : }
278 37645 : }
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 24708382 : relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
285 : {
286 24708382 : unsigned i;
287 24708382 : bitmap_iterator bi;
288 52104663 : EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
289 : {
290 27396281 : tree ssa = ssa_name (i);
291 54792562 : if (ssa && !SSA_NAME_IN_FREE_LIST (ssa))
292 : {
293 27396281 : const_bitmap ssa_equiv = equiv_set (ssa, bb);
294 27396281 : if (ssa_equiv == equivs)
295 27105002 : bitmap_set_bit (b, i);
296 : }
297 : }
298 24708382 : }
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 139818933 : relation_oracle::query (gimple *s, tree ssa1, tree ssa2)
306 : {
307 139818933 : if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
308 : return VREL_VARYING;
309 60304893 : 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 49305569 : relation_oracle::query (edge e, tree ssa1, tree ssa2)
318 : {
319 49305569 : basic_block bb;
320 49305569 : 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 36200883 : if (!single_pred_p (e->dest))
327 34256564 : bb = e->src;
328 : else
329 : bb = e->dest;
330 :
331 36200883 : 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 216294095 : equiv_chain::find (unsigned ssa)
348 : {
349 216294095 : 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 216294095 : if (bitmap_bit_p (m_names, ssa))
353 : {
354 246675340 : for (ptr = m_next; ptr; ptr = ptr->m_next)
355 246675340 : if (bitmap_bit_p (ptr->m_names, ssa))
356 : break;
357 : }
358 216294095 : return ptr;
359 : }
360 :
361 : // Dump the names in this equivalence set.
362 :
363 : void
364 10 : equiv_chain::dump (FILE *f) const
365 : {
366 10 : bitmap_iterator bi;
367 10 : unsigned i;
368 :
369 10 : if (!m_names || bitmap_empty_p (m_names))
370 1 : return;
371 9 : fprintf (f, "Equivalence set : [");
372 9 : unsigned c = 0;
373 24 : EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
374 : {
375 15 : if (ssa_name (i))
376 : {
377 15 : if (c++)
378 6 : fprintf (f, ", ");
379 15 : print_generic_expr (f, ssa_name (i), TDF_SLIM);
380 : }
381 : }
382 9 : fprintf (f, "]\n");
383 : }
384 :
385 : // Instantiate an equivalency oracle.
386 :
387 27589038 : equiv_oracle::equiv_oracle ()
388 : {
389 27589038 : bitmap_obstack_initialize (&m_bitmaps);
390 27589038 : m_equiv.create (0);
391 27589038 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
392 27589038 : m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
393 27589038 : bitmap_tree_view (m_equiv_set);
394 27589038 : obstack_init (&m_chain_obstack);
395 27589038 : m_name_info.create (0);
396 55178076 : m_name_info.safe_grow_cleared (num_ssa_names + 1);
397 27589038 : m_partial.create (0);
398 55178076 : 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 27589038 : m_lhs_equiv_set_p = BITMAP_ALLOC (&m_bitmaps);
402 27589038 : bitmap_tree_view (m_lhs_equiv_set_p);
403 27589038 : }
404 :
405 : // Destruct an equivalency oracle.
406 :
407 27589038 : equiv_oracle::~equiv_oracle ()
408 : {
409 27589038 : m_partial.release ();
410 27589038 : m_name_info.release ();
411 27589038 : obstack_free (&m_chain_obstack, NULL);
412 27589038 : m_equiv.release ();
413 27589038 : bitmap_obstack_release (&m_bitmaps);
414 27589038 : }
415 :
416 : // Add a partial equivalence R between OP1 and OP2. Return false if no
417 : // new relation is added.
418 :
419 : bool
420 10518482 : equiv_oracle::add_partial_equiv (relation_kind r, tree op1, tree op2)
421 : {
422 10518482 : int v1 = SSA_NAME_VERSION (op1);
423 10518482 : int v2 = SSA_NAME_VERSION (op2);
424 10518482 : int prec2 = TYPE_PRECISION (TREE_TYPE (op2));
425 10518482 : int bits = pe_to_bits (r);
426 10518482 : gcc_checking_assert (bits && prec2 >= bits);
427 :
428 21036964 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
429 9956 : m_partial.safe_grow_cleared (num_ssa_names + 1);
430 21036964 : gcc_checking_assert (v1 < (int)m_partial.length ()
431 : && v2 < (int)m_partial.length ());
432 :
433 10518482 : pe_slice &pe1 = m_partial[v1];
434 10518482 : pe_slice &pe2 = m_partial[v2];
435 :
436 10518482 : 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 10518273 : if (pe2.members)
462 : {
463 : // If there are no uses of op1, do not register.
464 781640 : if (has_zero_uses (op1))
465 : return false;
466 766984 : 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 766984 : pe1.code = pe_min (r, pe2.code);
470 766984 : pe1.members = pe2.members;
471 766984 : bitmap_set_bit (pe1.members, v1);
472 : }
473 : else
474 : {
475 : // If there are no uses of either operand, do not register.
476 9736633 : 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 9581742 : pe2.code = bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2)));
480 9581742 : if (pe2.code == VREL_VARYING)
481 : return false;
482 9520593 : pe2.ssa_base = op2;
483 9520593 : pe2.members = BITMAP_ALLOC (&m_bitmaps);
484 9520593 : bitmap_set_bit (pe2.members, v2);
485 9520593 : pe1.ssa_base = op2;
486 9520593 : pe1.code = r;
487 9520593 : pe1.members = pe2.members;
488 9520593 : 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 64475234 : equiv_oracle::partial_equiv_set (tree name)
498 : {
499 64475234 : int v = SSA_NAME_VERSION (name);
500 128950468 : if (v >= (int)m_partial.length ())
501 : return NULL;
502 64475234 : 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 109402056 : equiv_oracle::partial_equiv (tree ssa1, tree ssa2, tree *base) const
511 : {
512 109402056 : int v1 = SSA_NAME_VERSION (ssa1);
513 109402056 : int v2 = SSA_NAME_VERSION (ssa2);
514 :
515 218804112 : if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ())
516 : return VREL_VARYING;
517 :
518 109400913 : const pe_slice &pe1 = m_partial[v1];
519 109400913 : const pe_slice &pe2 = m_partial[v2];
520 109400913 : if (pe1.members && pe2.members == pe1.members)
521 : {
522 36667 : if (base)
523 0 : *base = pe1.ssa_base;
524 36667 : return pe_min (pe1.code, pe2.code);
525 : }
526 : return VREL_VARYING;
527 : }
528 :
529 : void
530 21053115 : equiv_oracle::register_equiv_block (unsigned v, unsigned bbi)
531 : {
532 21053115 : if (v >= m_name_info.length ())
533 60 : m_name_info.safe_grow_cleared (num_ssa_names + 1);
534 :
535 21053115 : if (!m_name_info[v].m_block_list)
536 9619101 : m_name_info[v].m_block_list = BITMAP_ALLOC (&m_bitmaps);
537 :
538 21053115 : bitmap_set_bit (m_name_info[v].m_block_list, bbi);
539 21053115 : }
540 :
541 : void
542 15627263 : equiv_oracle::register_equiv_block (const_bitmap names, basic_block bb)
543 : {
544 15627263 : bitmap_iterator bi;
545 15627263 : unsigned v;
546 :
547 36649965 : EXECUTE_IF_SET_IN_BITMAP (names, 0, v, bi)
548 21022702 : register_equiv_block (v, bb->index);
549 15627263 : }
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 180807448 : equiv_oracle::equiv_set (tree ssa, basic_block bb)
556 : {
557 : // Search the dominator tree for an equivalency.
558 180807448 : equiv_chain *equiv = find_equiv_dom (ssa, bb);
559 180807448 : if (equiv)
560 22772071 : return equiv->m_names;
561 :
562 : // Otherwise return a cached equiv set containing just this SSA.
563 158035377 : unsigned v = SSA_NAME_VERSION (ssa);
564 158035377 : if (v >= m_name_info.length ())
565 9630 : m_name_info.safe_grow_cleared (num_ssa_names + 1);
566 :
567 158035377 : if (!m_name_info[v].m_self_equiv)
568 : {
569 39303903 : m_name_info[v].m_self_equiv = BITMAP_ALLOC (&m_bitmaps);
570 39303903 : bitmap_set_bit (m_name_info[v].m_self_equiv, v);
571 : }
572 158035377 : 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 159470552 : equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
605 : {
606 318941104 : if (bb >= (int)m_equiv.length () || !m_equiv[bb])
607 : return NULL;
608 :
609 72051482 : 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 201105301 : equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
617 : {
618 201105301 : 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 201105301 : 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 161915159 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
627 : {
628 159470552 : equiv_chain *ptr = find_equiv_block (v, bb->index);
629 159470552 : 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 91343 : equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
639 : {
640 : // V will have an equivalency now.
641 91343 : bitmap_set_bit (m_equiv_set, v);
642 :
643 : // If that equiv chain is in this block, simply use it.
644 91343 : if (equiv->m_bb == bb)
645 : {
646 30413 : bitmap_set_bit (equiv->m_names, v);
647 30413 : bitmap_set_bit (m_equiv[bb->index]->m_names, v);
648 : // Add BB to V.
649 30413 : register_equiv_block (v, bb->index);
650 30413 : 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 60930 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
656 60930 : valid_equivs (b, equiv->m_names, bb);
657 60930 : bitmap_set_bit (b, v);
658 : // Add BB to the all the equiv names.
659 60930 : register_equiv_block (b, bb);
660 60930 : 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 5281825 : 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 5281825 : if (equiv_1->m_bb == bb)
674 : {
675 3461484 : 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 3461484 : if (equiv_2->m_bb == bb)
679 1131878 : bitmap_clear (equiv_2->m_names);
680 : else
681 : {
682 : // Ensure the new names are in the summary for BB.
683 2329606 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
684 : // Add BB to the names in equiv2.
685 2329606 : 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 1820341 : if (equiv_2->m_bb == bb)
691 : {
692 2494 : valid_equivs (equiv_2->m_names, equiv_1->m_names, bb);
693 : // Ensure the new names are in the summary.
694 2494 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
695 : // Add BB to the names in equiv1.
696 2494 : register_equiv_block (equiv_1->m_names, bb);
697 2494 : return NULL;
698 : }
699 :
700 : // At this point, neither equivalence is from this block.
701 1817847 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
702 1817847 : valid_equivs (b, equiv_1->m_names, bb);
703 1817847 : valid_equivs (b, equiv_2->m_names, bb);
704 : // Add BB to the all the equiv names.
705 1817847 : register_equiv_block (b, bb);
706 1817847 : 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 9619101 : equiv_oracle::register_initial_def (tree ssa)
715 : {
716 9619101 : if (SSA_NAME_IS_DEFAULT_DEF (ssa))
717 : return;
718 9526638 : basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
719 :
720 : // If defining stmt is not in the IL, simply return.
721 9526638 : if (!bb)
722 : return;
723 9526637 : gcc_checking_assert (!find_equiv_dom (ssa, bb));
724 :
725 9526637 : unsigned v = SSA_NAME_VERSION (ssa);
726 9526637 : bitmap_set_bit (m_equiv_set, v);
727 9526637 : bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps);
728 9526637 : bitmap_set_bit (equiv_set, v);
729 9526637 : add_equiv_to_block (bb, equiv_set);
730 : }
731 :
732 : // Clear the equivalence lists and partial equivalencs for NAME.
733 :
734 : void
735 268535 : equiv_oracle::clear (tree name)
736 : {
737 268535 : unsigned v = SSA_NAME_VERSION (name);
738 : // Remove NAME from any blocks it is an equivalence in.
739 268535 : if (bitmap_bit_p (m_equiv_set, v))
740 : {
741 170 : gcc_checking_assert (m_name_info[v].m_block_list);
742 170 : bitmap_iterator bi;
743 170 : unsigned bbi;
744 :
745 442 : EXECUTE_IF_SET_IN_BITMAP (m_name_info[v].m_block_list, 0, bbi, bi)
746 : {
747 272 : if (bbi >= m_equiv.length ())
748 : break;
749 272 : if (!m_equiv[bbi])
750 0 : continue;
751 272 : equiv_chain *ptr = m_equiv[bbi]->find (v);
752 272 : if (ptr)
753 : {
754 272 : bitmap_clear_bit (ptr->m_names, v);
755 272 : bitmap_clear_bit (m_equiv[bbi]->m_names, v);
756 : }
757 : }
758 170 : bitmap_clear_bit (m_equiv_set, v);
759 170 : bitmap_clear (m_name_info[v].m_block_list);
760 : }
761 : // Eliminate any partial equivs.
762 268535 : if (v < m_partial.length ())
763 208867 : m_partial[v].members = NULL;
764 268535 : }
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 15904090 : equiv_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2)
777 : {
778 : // Process partial equivalencies.
779 15904090 : if (relation_partial_equiv_p (k))
780 10518482 : return add_partial_equiv (k, ssa1, ssa2);
781 :
782 : // Only handle equality relations.
783 5385608 : if (k != VREL_EQ)
784 : return false;
785 :
786 5385608 : unsigned v1 = SSA_NAME_VERSION (ssa1);
787 5385608 : 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 5385608 : if (!bitmap_bit_p (m_equiv_set, v1))
792 5203740 : register_initial_def (ssa1);
793 5385608 : if (!bitmap_bit_p (m_equiv_set, v2))
794 4415361 : register_initial_def (ssa2);
795 :
796 5385608 : equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
797 5385608 : equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
798 :
799 : // Check if they are the same set
800 5385608 : if (equiv_1 && equiv_1 == equiv_2)
801 : return false;
802 :
803 5384140 : bitmap equiv_set;
804 :
805 : // Case where we have 2 SSA_NAMEs that are not in any set.
806 5384140 : if (!equiv_1 && !equiv_2)
807 : {
808 10972 : bitmap_set_bit (m_equiv_set, v1);
809 10972 : bitmap_set_bit (m_equiv_set, v2);
810 :
811 10972 : equiv_set = BITMAP_ALLOC (&m_bitmaps);
812 10972 : bitmap_set_bit (equiv_set, v1);
813 10972 : bitmap_set_bit (equiv_set, v2);
814 : }
815 5373168 : else if (!equiv_1 && equiv_2)
816 23210 : equiv_set = register_equiv (bb, v1, equiv_2);
817 5349958 : else if (equiv_1 && !equiv_2)
818 68133 : equiv_set = register_equiv (bb, v2, equiv_1);
819 : else
820 5281825 : 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 5384140 : if (!equiv_set)
825 : return false;
826 :
827 1889749 : add_equiv_to_block (bb, equiv_set);
828 1889749 : 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 11416386 : equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
836 : {
837 11416386 : 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 11416386 : limit_check (bb);
842 11416386 : if (!m_equiv[bb->index])
843 : {
844 6601335 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
845 : sizeof (equiv_chain));
846 6601335 : ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
847 6601335 : bitmap_copy (ptr->m_names, equiv_set);
848 6601335 : ptr->m_bb = bb;
849 6601335 : ptr->m_next = NULL;
850 6601335 : m_equiv[bb->index] = ptr;
851 : }
852 :
853 : // Now create the element for this equiv set and initialize it.
854 11416386 : ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
855 11416386 : ptr->m_names = equiv_set;
856 11416386 : ptr->m_bb = bb;
857 22832772 : gcc_checking_assert (bb->index < (int)m_equiv.length ());
858 11416386 : ptr->m_next = m_equiv[bb->index]->m_next;
859 11416386 : m_equiv[bb->index]->m_next = ptr;
860 11416386 : bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
861 : // Add BB to the equiv set.
862 11416386 : register_equiv_block (equiv_set, bb);
863 11416386 : }
864 :
865 : // Make sure the BB vector is big enough and grow it if needed.
866 :
867 : void
868 11416386 : equiv_oracle::limit_check (basic_block bb)
869 : {
870 11416386 : int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
871 22832772 : if (i >= (int)m_equiv.length ())
872 47 : m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
873 11416386 : }
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 8 : equiv_chain *ptr = m_equiv[bb->index]->m_next;
886 18 : for (; ptr; ptr = ptr->m_next)
887 10 : ptr->dump (f);
888 : }
889 : // Look for partial equivalences defined in this block..
890 12774 : for (unsigned i = 0; i < num_ssa_names; i++)
891 : {
892 12517 : tree name = ssa_name (i);
893 17757 : if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name))
894 7277 : continue;
895 5240 : if (i >= m_partial.length ())
896 : break;
897 5240 : tree base = m_partial[i].ssa_base;
898 5240 : 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 12116809 : value_relation::intersect (value_relation &p)
945 : {
946 : // Save previous value
947 12116809 : relation_kind old = related;
948 :
949 12116809 : if (p.op1 () == op1 () && p.op2 () == op2 ())
950 12023988 : related = relation_intersect (kind (), p.kind ());
951 92821 : else if (p.op2 () == op1 () && p.op1 () == op2 ())
952 92821 : related = relation_intersect (kind (), relation_swap (p.kind ()));
953 : else
954 : return false;
955 :
956 12116809 : 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 55814563 : value_relation::apply_transitive (const value_relation &rel)
982 : {
983 55814563 : 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 55814563 : if (rel.op1 () == name2)
988 : {
989 : // A < B B < C
990 55814563 : if (rel.op2 () == name1)
991 : return false;
992 42163728 : k = relation_transitive (kind (), rel.kind ());
993 42163728 : if (k != VREL_VARYING)
994 : {
995 29459207 : related = k;
996 29459207 : name2 = rel.op2 ();
997 29459207 : 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 89705248 : value_relation::create_trio (tree lhs, tree op1, tree op2)
1049 : {
1050 89705248 : relation_kind lhs_1;
1051 89705248 : if (lhs == name1 && op1 == name2)
1052 122122 : lhs_1 = related;
1053 89583126 : else if (lhs == name2 && op1 == name1)
1054 378887 : lhs_1 = relation_swap (related);
1055 : else
1056 : lhs_1 = VREL_VARYING;
1057 :
1058 89705248 : relation_kind lhs_2;
1059 89705248 : if (lhs == name1 && op2 == name2)
1060 161733 : lhs_2 = related;
1061 89543515 : else if (lhs == name2 && op2 == name1)
1062 834191 : lhs_2 = relation_swap (related);
1063 : else
1064 : lhs_2 = VREL_VARYING;
1065 :
1066 89705248 : relation_kind op_op;
1067 89705248 : if (op1 == name1 && op2 == name2)
1068 59658688 : op_op = related;
1069 30046560 : else if (op1 == name2 && op2 == name1)
1070 0 : op_op = relation_swap (related);
1071 30046560 : else if (op1 == op2)
1072 : op_op = VREL_EQ;
1073 : else
1074 30018044 : op_op = VREL_VARYING;
1075 :
1076 89705248 : return relation_trio (lhs_1, lhs_2, op_op);
1077 : }
1078 :
1079 : // Dump the relation to file F.
1080 :
1081 : void
1082 39751 : value_relation::dump (FILE *f) const
1083 : {
1084 39751 : if (!name1 || !name2)
1085 : {
1086 0 : fprintf (f, "no relation registered");
1087 0 : return;
1088 : }
1089 39751 : fputc ('(', f);
1090 39751 : print_generic_expr (f, op1 (), TDF_SLIM);
1091 39751 : print_relation (f, kind ());
1092 39751 : print_generic_expr (f, op2 (), TDF_SLIM);
1093 39751 : 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 88020835 : relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
1184 : {
1185 88020835 : 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 62753890 : 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 8250916 : for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
1195 : {
1196 7240252 : unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1197 7240252 : unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1198 7240252 : if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
1199 3298618 : return ptr->kind ();
1200 3941634 : if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
1201 169468 : 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 55178076 : frontier_data::frontier_data (bitmap_obstack *obstack, bool rhs)
1213 : {
1214 55178076 : m_known.create (0);
1215 55178076 : m_visited = BITMAP_ALLOC (obstack);
1216 55178076 : m_root = NULL_TREE;
1217 55178076 : m_rhs = rhs;
1218 55178076 : }
1219 :
1220 : // Record that the root of this search is related to ssa version V by REL.
1221 :
1222 : void
1223 74933760 : frontier_data::set_known (unsigned v, relation_kind rel)
1224 : {
1225 74933760 : if (m_known.length () <= v)
1226 8453086 : m_known.safe_grow_cleared (num_ssa_names + 1);
1227 74933760 : m_known[v] = rel;
1228 74933760 : }
1229 :
1230 : // Return what the root of this search is known to be relative to ssa version V.
1231 :
1232 : relation_kind
1233 34668434 : frontier_data::known_relation (unsigned v) const
1234 : {
1235 34668434 : if (v < m_known.length ())
1236 34668434 : 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 55452882 : frontier_data::clear_search ()
1245 : {
1246 55452882 : unsigned i;
1247 55452882 : bitmap_iterator bi;
1248 130361150 : EXECUTE_IF_SET_IN_BITMAP (m_visited, 0, i, bi)
1249 : {
1250 149816536 : if (i < m_known.length ())
1251 74908268 : m_known[i] = VREL_VARYING;
1252 : }
1253 55452882 : bitmap_clear (m_visited);
1254 55452882 : m_root = NULL_TREE;
1255 55452882 : }
1256 :
1257 : // ------------------------------------------------------------------------
1258 : // Instantiate a relation oracle.
1259 :
1260 55178076 : dom_oracle::dom_oracle () : m_lhs_search (&m_bitmaps, false),
1261 27589038 : m_rhs_search (&m_bitmaps, true)
1262 : {
1263 27589038 : m_relations.create (0);
1264 27589038 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1265 27589038 : m_relation_set = BITMAP_ALLOC (&m_bitmaps);
1266 27589038 : m_block_list.create (0);
1267 55178076 : m_block_list.safe_grow_cleared (num_ssa_names + 1);
1268 27589038 : m_tmp = BITMAP_ALLOC (&m_bitmaps);
1269 27589038 : m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
1270 27589038 : m_near.create (0);
1271 27589038 : m_worklist.create (0);
1272 27589038 : m_wl_ix = 0;
1273 27589038 : }
1274 :
1275 : // Destruct a relation oracle.
1276 :
1277 55178076 : dom_oracle::~dom_oracle ()
1278 : {
1279 27589038 : m_worklist.release ();
1280 27589038 : m_near.release ();
1281 27589038 : m_block_list.release ();
1282 27589038 : m_relations.release ();
1283 55178076 : }
1284 :
1285 : // Remove any relations with NAME from this list.
1286 :
1287 : void
1288 717 : relation_chain_head::clear (tree name)
1289 : {
1290 717 : unsigned v = SSA_NAME_VERSION (name);
1291 717 : if (!m_names || !bitmap_bit_p (m_names, v))
1292 : return;
1293 :
1294 717 : relation_chain *ptr, *last = NULL;;
1295 :
1296 1465 : for (ptr = m_head; ptr; ptr = ptr->m_next)
1297 : {
1298 748 : tree op1 = ptr->op1 ();
1299 748 : tree op2 = ptr->op2 ();
1300 : // Delink any elements with NAME.
1301 748 : if (op1 == name || op2 == name)
1302 : {
1303 672 : if (!last)
1304 613 : m_head = ptr->m_next;
1305 : else
1306 59 : last->m_next = ptr->m_next;
1307 672 : m_num_relations--;
1308 : }
1309 : else
1310 : last = ptr;
1311 : }
1312 : // And remove name from the possible relations in this block bitfield.
1313 717 : bitmap_clear_bit (m_names, v);
1314 : }
1315 :
1316 : // Remove any relations involving NAME from the DOM oracle
1317 :
1318 : void
1319 268535 : dom_oracle::clear (tree name)
1320 : {
1321 268535 : equiv_oracle::clear (name);
1322 268535 : unsigned v = SSA_NAME_VERSION (name);
1323 268535 : if (bitmap_bit_p (m_relation_set, v))
1324 : {
1325 475 : gcc_checking_assert (m_block_list[v]);
1326 475 : bitmap_iterator bi;
1327 475 : unsigned bbi;
1328 :
1329 1192 : EXECUTE_IF_SET_IN_BITMAP (m_block_list[v], 0, bbi, bi)
1330 : {
1331 717 : if (bbi >= m_relations.length())
1332 : break;
1333 717 : m_relations[bbi].clear (name);
1334 : }
1335 475 : bitmap_clear_bit (m_relation_set, v);
1336 475 : bitmap_clear (m_block_list[v]);
1337 : }
1338 268535 : }
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 34419937 : relation_oracle::record (gimple *stmt, relation_kind k, tree op1, tree op2)
1345 : {
1346 34419937 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1347 34419937 : gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
1348 34419937 : gcc_checking_assert (stmt && gimple_bb (stmt));
1349 :
1350 : // Don't register lack of a relation.
1351 34419937 : 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 34419937 : if (k == VREL_EQ && is_a<gphi *> (stmt))
1359 : {
1360 2156475 : tree phi_def = gimple_phi_result (stmt);
1361 2156475 : gcc_checking_assert (phi_def == op1 || phi_def == op2);
1362 2156475 : tree arg = op2;
1363 2156475 : if (phi_def == op2)
1364 0 : arg = op1;
1365 2156475 : 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 82847603 : if (m_lhs_equiv_set_p && relation_equiv_p (k)
1372 49076515 : && gimple_get_lhs (stmt) == op1)
1373 : {
1374 14656578 : if (!bitmap_set_bit (m_lhs_equiv_set_p, SSA_NAME_VERSION (op1)))
1375 : return false;
1376 : }
1377 33771088 : bool ret = record (gimple_bb (stmt), k, op1, op2);
1378 :
1379 33771088 : if (ret && dump_file && (dump_flags & TDF_DETAILS))
1380 : {
1381 39232 : value_relation vr (k, op1, op2);
1382 39232 : fprintf (dump_file, " Registering value_relation ");
1383 39232 : vr.dump (dump_file);
1384 39232 : fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
1385 39232 : 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 7459190 : relation_oracle::record (edge e, relation_kind k, tree op1, tree op2)
1395 : {
1396 7459190 : gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
1397 7459190 : 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 7459190 : if (k == VREL_VARYING || !single_pred_p (e->dest))
1402 : return false;
1403 :
1404 7459190 : bool ret = record (e->dest, k, op1, op2);
1405 :
1406 7459190 : 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 40168164 : 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 40168164 : if (op1 == op2)
1426 : return false;
1427 :
1428 : // Do not register an impossible relation.
1429 40157302 : if (k == VREL_UNDEFINED)
1430 : return false;
1431 :
1432 : // Equivalencies are handled by the equivalence oracle.
1433 40157302 : if (relation_equiv_p (k))
1434 15904090 : return equiv_oracle::record (bb, k, op1, op2);
1435 : else
1436 : {
1437 24253212 : relation_chain *ptr = search_and_merge_relation (bb, k, op1, op2);
1438 24253212 : return ptr != NULL;
1439 : }
1440 : }
1441 :
1442 : void
1443 46953976 : dom_oracle::record_relation_block (unsigned v, unsigned bbi)
1444 : {
1445 46953976 : if (v>= m_block_list.length ())
1446 10504 : m_block_list.safe_grow_cleared (num_ssa_names + 1);
1447 :
1448 46953976 : if (!m_block_list[v])
1449 32289528 : m_block_list[v] = BITMAP_ALLOC (&m_bitmaps);
1450 :
1451 46953976 : bitmap_set_bit (m_block_list[v], bbi);
1452 46953976 : }
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 23520032 : dom_oracle::create_relation_in_bb (basic_block bb, relation_kind k, tree op1,
1460 : tree op2)
1461 : {
1462 23520032 : int bbi = bb->index;
1463 :
1464 47040064 : if (bbi >= (int)m_relations.length())
1465 126 : m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1466 :
1467 23520032 : if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
1468 : return NULL;
1469 23476988 : 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 23476988 : relation_chain *ptr;
1475 :
1476 : // Summary bitmap indicating what ssa_names have relations in this BB.
1477 23476988 : bitmap bm = m_relations[bbi].m_names;
1478 23476988 : if (!bm)
1479 16817459 : bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
1480 23476988 : unsigned v1 = SSA_NAME_VERSION (op1);
1481 23476988 : unsigned v2 = SSA_NAME_VERSION (op2);
1482 :
1483 : // Assert there is no existing relation.
1484 23476988 : gcc_checking_assert (find_relation_block (bbi, op1, op2, NULL)
1485 : == VREL_VARYING);
1486 :
1487 23476988 : bitmap_set_bit (bm, v1);
1488 23476988 : bitmap_set_bit (bm, v2);
1489 23476988 : bitmap_set_bit (m_relation_set, v1);
1490 23476988 : bitmap_set_bit (m_relation_set, v2);
1491 23476988 : record_relation_block (v1, bbi);
1492 23476988 : record_relation_block (v2, bbi);
1493 :
1494 23476988 : ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1495 : sizeof (relation_chain));
1496 23476988 : ptr->set_relation (k, op1, op2);
1497 23476988 : ptr->m_next = m_relations[bbi].m_head;
1498 23476988 : m_relations[bbi].m_head = ptr;
1499 23476988 : 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 35636843 : 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 35636843 : gcc_checking_assert (k != VREL_VARYING && k != VREL_UNDEFINED
1513 : && k != VREL_EQ);
1514 :
1515 35636843 : relation_chain *ptr;
1516 35636843 : 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 35636843 : 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 12116811 : if (relation_intersect (curr, k) == VREL_UNDEFINED)
1525 : return NULL;
1526 : // If there was no change, return no record.
1527 12116809 : value_relation vr (k, op1, op2);
1528 12116809 : if (!ptr->intersect (vr))
1529 : return NULL;
1530 215452 : return ptr;
1531 : }
1532 :
1533 : // Create the relation in this block.
1534 23520032 : ptr = create_relation_in_bb (bb, k, op1, op2);
1535 23520032 : 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 23476988 : curr = find_relation_dom (get_immediate_dominator (CDI_DOMINATORS, bb),
1541 : op1, op2);
1542 23476988 : if (curr != VREL_VARYING)
1543 : {
1544 2992586 : 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 2992586 : if (curr != k && curr != VREL_UNDEFINED)
1548 158627 : ptr->set_relation (curr, op1, op2);
1549 : }
1550 : }
1551 23520032 : 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 34679649 : dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
1559 : const_bitmap b2) const
1560 : {
1561 34679649 : if (bb >= m_relations.length())
1562 : return VREL_VARYING;
1563 :
1564 34679649 : 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 12109701 : dom_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
1572 : {
1573 12109701 : relation_kind r;
1574 12109701 : 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 12109701 : if (!bitmap_intersect_p (m_relation_set, b1)
1579 12109701 : || !bitmap_intersect_p (m_relation_set, b2))
1580 : return VREL_VARYING;
1581 :
1582 : // Search each block in the DOM tree checking.
1583 36472396 : for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1584 : {
1585 34679649 : r = find_relation_block (bb->index, b1, b2);
1586 34679649 : 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 673190407 : dom_oracle::find_relation_block (int bb, tree ssa1, tree ssa2,
1598 : relation_chain **obj) const
1599 : {
1600 1346380814 : if (bb >= (int)m_relations.length())
1601 : return VREL_VARYING;
1602 :
1603 673178566 : const_bitmap bm = m_relations[bb].m_names;
1604 673178566 : if (!bm)
1605 : return VREL_VARYING;
1606 :
1607 273763596 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1608 273763596 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1609 :
1610 : // If both b1 and b2 aren't referenced in this block, cant be a relation
1611 273763596 : if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1612 : return VREL_VARYING;
1613 :
1614 15402728 : relation_chain *ptr;
1615 24373225 : for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1616 : {
1617 24079894 : tree op1 = ptr->op1 ();
1618 24079894 : tree op2 = ptr->op2 ();
1619 24079894 : if (ssa1 == op1 && ssa2 == op2)
1620 : {
1621 14919504 : if (obj)
1622 12023990 : *obj = ptr;
1623 14919504 : return ptr->kind ();
1624 : }
1625 9160390 : if (ssa1 == op2 && ssa2 == op1)
1626 : {
1627 189893 : if (obj)
1628 92821 : *obj = ptr;
1629 189893 : 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 27726441 : dom_oracle::recomputed_relation (basic_block orig_bb, tree ssa1,
1642 : tree ssa2) const
1643 : {
1644 27726441 : if (ssa1 == ssa2)
1645 : return VREL_EQ;
1646 27726441 : if (!orig_bb)
1647 : return VREL_VARYING;
1648 55452882 : gori_map *gori_ssa = get_range_query (cfun)->gori_ssa ();
1649 27726441 : if (!gori_ssa)
1650 : return VREL_VARYING;
1651 40559552 : gimple_outgoing_range &gori = get_range_query (cfun)->gori ();
1652 :
1653 : // Both ssa1 and ssa2 must be exported somewhere.
1654 20279776 : if (!gori_ssa->is_export_p (ssa1) || !gori_ssa->is_export_p (ssa2))
1655 : return VREL_VARYING;
1656 :
1657 13632017 : relation_kind result = VREL_VARYING;
1658 13632017 : use_operand_p use_p;
1659 13632017 : 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 101059792 : FOR_EACH_IMM_USE_FAST (use_p, iter, ssa1)
1664 : {
1665 87427775 : bool reversed = false;
1666 87427775 : gimple *s = USE_STMT (use_p);
1667 :
1668 : // S must be a binary assignment LHS = op1 op2
1669 87427775 : if (!is_gimple_assign (s) || gimple_num_ops (s) != 3)
1670 87245154 : 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 12006887 : basic_block sbb = gimple_bb (s);
1675 21632727 : if (!sbb || sbb == orig_bb
1676 12006887 : || !dominated_by_p (CDI_DOMINATORS, orig_bb, sbb))
1677 9625840 : continue;
1678 :
1679 2381047 : gimple_range_op_handler s_handler (s);
1680 2381047 : if (!s_handler)
1681 83 : continue;
1682 :
1683 2380964 : if (s_handler.operand1 () == ssa1)
1684 : {
1685 : // op1 == ssa1, move on if op2 != ssa2.
1686 1803099 : if (s_handler.operand2 () != ssa2)
1687 1602845 : continue;
1688 : }
1689 : // Otherwise only move on if op1 == ssa2 && op2 == ssa1.
1690 577865 : else if (s_handler.operand1 () != ssa2 || s_handler.operand2 () != ssa1)
1691 520255 : 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 257864 : edge e = NULL, se;
1702 257864 : edge_iterator ei;
1703 425322 : FOR_EACH_EDGE (se, ei, sbb->succs)
1704 551399 : if (single_pred_p (se->dest)
1705 383941 : && dominated_by_p (CDI_DOMINATORS, orig_bb, se->dest))
1706 : {
1707 : e = se;
1708 : break;
1709 : }
1710 257864 : if (!e)
1711 41381 : continue;
1712 :
1713 216483 : int_range_max edge_range;
1714 216483 : gimple *stmt = gori.edge_range_p (edge_range, e);
1715 216483 : if (!stmt)
1716 1869 : 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 214614 : tree lhs_s = s_handler.lhs ();
1724 214614 : value_range lhs_range (edge_range);
1725 :
1726 771629 : while (stmt && stmt != s)
1727 : {
1728 374394 : bool ret;
1729 374394 : gimple_range_op_handler handler (stmt);
1730 374394 : if (!handler)
1731 : break;
1732 :
1733 373648 : tree op1 = handler.operand1 ();
1734 373648 : tree op2 = handler.operand2 ();
1735 373648 : value_range op1_range (TREE_TYPE (op1));
1736 373648 : value_range op2_range;
1737 :
1738 : // Follow the operand whose dependency chain reaches S's LHS.
1739 373648 : bool op1_dep = gimple_range_ssa_p (op1)
1740 373648 : && (op1 == lhs_s || gori_ssa->in_chain_p (lhs_s, op1));
1741 373648 : bool op2_dep = gimple_range_ssa_p (op2)
1742 373648 : && (op2 == lhs_s || gori_ssa->in_chain_p (lhs_s, op2));
1743 373648 : if (op1_dep == op2_dep)
1744 : break;
1745 :
1746 346015 : if (op1_dep)
1747 : {
1748 233960 : if (!op2)
1749 28015 : ret = handler.calc_op1 (op1_range, lhs_range);
1750 : else
1751 : {
1752 205945 : op2_range.set_range_class (TREE_TYPE (op2));
1753 411890 : get_range_query (cfun)->range_on_entry (op2_range, orig_bb,
1754 : op2);
1755 205945 : ret = handler.calc_op1 (op1_range, lhs_range, op2_range);
1756 : }
1757 233960 : if (!ret)
1758 : break;
1759 230658 : lhs_range = op1_range;
1760 230658 : stmt = SSA_NAME_DEF_STMT (op1);
1761 : }
1762 : else
1763 : {
1764 112055 : op2_range.set_range_class (TREE_TYPE (op2));
1765 224110 : get_range_query (cfun)->range_on_entry (op1_range, orig_bb, op1);
1766 112055 : ret = handler.calc_op2 (op2_range, lhs_range, op1_range);
1767 112055 : if (!ret)
1768 : break;
1769 111743 : lhs_range = op2_range;
1770 111743 : stmt = SSA_NAME_DEF_STMT (op2);
1771 : }
1772 :
1773 : // Bail if the chain leaves SBB.
1774 342401 : if (!stmt || gimple_bb (stmt) != sbb)
1775 : break;
1776 373648 : }
1777 :
1778 214614 : if (stmt != s)
1779 31993 : continue;
1780 :
1781 : // LHS_RANGE is now S's LHS as it is known in ORIG_BB.
1782 182621 : value_range op1_range (TREE_TYPE (s_handler.operand1 ()));
1783 182621 : value_range op2_range (TREE_TYPE (s_handler.operand2 ()));
1784 365242 : get_range_query (cfun)->range_on_entry (op1_range, orig_bb,
1785 : s_handler.operand1 ());
1786 365242 : get_range_query (cfun)->range_on_entry (op2_range, orig_bb,
1787 : s_handler.operand2 ());
1788 182621 : relation_kind r = s_handler.op1_op2_relation (lhs_range, op1_range,
1789 182621 : op2_range);
1790 182621 : if (reversed)
1791 41561 : r = relation_swap (r);
1792 182621 : relation_kind k = relation_intersect (result, r);
1793 182621 : if (k != VREL_UNDEFINED)
1794 182621 : result = k;
1795 216483 : }
1796 13632017 : 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 23476988 : dom_oracle::find_relation_dom (basic_block start_bb, tree ssa1, tree ssa2) const
1804 : {
1805 23476988 : relation_kind r;
1806 23476988 : unsigned v1 = SSA_NAME_VERSION (ssa1);
1807 23476988 : unsigned v2 = SSA_NAME_VERSION (ssa2);
1808 : // IF either name does not occur in a relation anywhere, there isn't one.
1809 23476988 : if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1810 : return VREL_VARYING;
1811 611083990 : for (basic_block bb = start_bb;
1812 634560978 : bb;
1813 611083990 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1814 : {
1815 614076576 : r = find_relation_block (bb->index, ssa1, ssa2);
1816 614076576 : 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 81990311 : dom_oracle::nearest_relations (tree name, basic_block bb)
1830 : {
1831 81990311 : if (TREE_CODE (name) != SSA_NAME)
1832 : return NULL;
1833 :
1834 81990311 : unsigned v = SSA_NAME_VERSION (name);
1835 81990311 : 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 77680235 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1843 77680235 : bool at_def = false;
1844 :
1845 77680235 : m_near.truncate (0);
1846 1485893860 : for (; bb && !at_def; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1847 : {
1848 1379845453 : at_def = (bb == def_bb);
1849 :
1850 2759690906 : if (bb->index >= (int) m_relations.length ())
1851 1616 : continue;
1852 :
1853 1379843837 : const_bitmap bm = m_relations[bb->index].m_names;
1854 1379843837 : if (!bm || !bitmap_bit_p (bm, v))
1855 1330531768 : continue;
1856 :
1857 49312069 : for (relation_chain *ptr = m_relations[bb->index].m_head;
1858 182756585 : ptr; ptr = ptr->m_next)
1859 : {
1860 133444516 : if (v == SSA_NAME_VERSION (ptr->op1 ())
1861 133444516 : && !SSA_NAME_IN_FREE_LIST (ptr->op2 ()))
1862 33641515 : m_near.safe_push ({ ptr->kind (), ptr->op2 (), bb });
1863 99803001 : else if (v == SSA_NAME_VERSION (ptr->op2 ())
1864 99803001 : && !SSA_NAME_IN_FREE_LIST (ptr->op1 ()))
1865 44918760 : m_near.safe_push ({ relation_swap (ptr->kind ()),
1866 22459380 : ptr->op1 (), bb });
1867 : }
1868 :
1869 1379845457 : 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 27726441 : dom_oracle::cache_relation (basic_block bb, relation_kind k, tree op1,
1884 : tree op2)
1885 : {
1886 27726441 : 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 27726441 : if (k == VREL_VARYING || k == VREL_UNDEFINED || relation_equiv_p (k))
1891 : return;
1892 11383631 : 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 55452882 : dom_oracle::start_search (frontier_data &side, tree root, const_bitmap equiv,
1901 : basic_block bb)
1902 : {
1903 55452882 : side.m_root = root;
1904 :
1905 55452882 : unsigned root_v = SSA_NAME_VERSION (root);
1906 55452882 : m_worklist.safe_push ({ VREL_EQ, root, bb, side.m_rhs });
1907 55452882 : bitmap_set_bit (side.m_visited, root_v);
1908 55452882 : side.set_known (root_v, VREL_EQ);
1909 :
1910 55452882 : unsigned i;
1911 55452882 : bitmap_iterator bi;
1912 114405921 : 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 58953039 : tree name = ssa_name (i);
1917 62453195 : if (i == root_v || !name || SSA_NAME_IN_FREE_LIST (name))
1918 55452883 : continue;
1919 3500156 : m_worklist.safe_push ({ VREL_EQ, name, bb, side.m_rhs });
1920 3500156 : bitmap_set_bit (side.m_visited, i);
1921 3500156 : side.set_known (i, VREL_EQ);
1922 : }
1923 55452882 : }
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 18052625 : dom_oracle::add_to_frontier (frontier_data &side, tree name, relation_kind rel,
1930 : basic_block bb)
1931 : {
1932 18052625 : unsigned v = SSA_NAME_VERSION (name);
1933 18052625 : if (!side.visited_p (v))
1934 : {
1935 15955230 : bitmap_set_bit (side.m_visited, v);
1936 15955230 : side.set_known (v, rel);
1937 15955230 : m_worklist.safe_push ({ rel, name, bb, side.m_rhs });
1938 15955230 : return;
1939 : }
1940 :
1941 : // NAME already had a relation, so intersect the two and requeue NAME if
1942 : // there is an improvement.
1943 2097395 : relation_kind curr = side.known_relation (v);
1944 2097395 : relation_kind k = relation_intersect (curr, rel);
1945 2097395 : if (k != curr && k != VREL_UNDEFINED)
1946 : {
1947 25492 : side.set_known (v, k);
1948 25492 : 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 81990311 : dom_oracle::expand_frontier (frontier_element w, basic_block bb,
1959 : relation_kind &result)
1960 : {
1961 81990311 : frontier_data &self = w.rhs ? m_rhs_search : m_lhs_search;
1962 81990311 : frontier_data &other = w.rhs ? m_lhs_search : m_rhs_search;
1963 :
1964 81990311 : 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 81990311 : basic_block found = nearest_relations (w.name, w.bb);
1972 81990311 : if (!found)
1973 : return false;
1974 :
1975 93720044 : 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 55814563 : value_relation path (w.rel, self.m_root, w.name);
1980 55814563 : value_relation near_rel (m_near[i].rel, w.name, m_near[i].name);
1981 :
1982 55814563 : if (!path.apply_transitive (near_rel))
1983 26355356 : continue;
1984 :
1985 29459207 : relation_kind kind = path.kind ();
1986 29459207 : tree next = path.op2 ();
1987 29459207 : 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 29459207 : if (other.visited_p (nv))
1992 : {
1993 12180934 : relation_kind k
1994 12180934 : = relation_transitive (kind,
1995 : relation_swap (other.known_relation (nv)));
1996 : // If the result is not VARYING, we have a match.
1997 12180934 : if (k != VREL_VARYING)
1998 : {
1999 11406582 : result = w.rhs ? relation_swap (k) : k;
2000 11406582 : 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 11406582 : return true;
2010 : }
2011 : }
2012 :
2013 : // Add to this side's frontier if it has not visited NEXT yet.
2014 18052625 : 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 37905481 : basic_block idom = get_immediate_dominator (CDI_DOMINATORS, found);
2022 37905481 : if (idom && gimple_bb (SSA_NAME_DEF_STMT (w.name)) != found)
2023 20390105 : 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 27726441 : 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 27726441 : start_search (m_lhs_search, lhs, lhs_equiv, bb);
2039 27726441 : start_search (m_rhs_search, rhs, rhs_equiv, bb);
2040 :
2041 27726441 : relation_kind result = VREL_VARYING;
2042 :
2043 : // Each expansion walks the dominator tree looking for the next block with
2044 : // a relation.
2045 27726441 : unsigned budget = param_transitive_relations_work_bound;
2046 :
2047 27726441 : 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 98310170 : while (m_wl_ix < m_worklist.length ())
2058 : {
2059 82010073 : if (!budget--)
2060 : {
2061 19762 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_RELATION))
2062 0 : fprintf (dump_file, " search budget exhausted\n");
2063 : break;
2064 : }
2065 :
2066 81990311 : if (expand_frontier (m_worklist[m_wl_ix++], bb, result))
2067 : break;
2068 : }
2069 :
2070 : // Clear search state for reuse.
2071 27726441 : m_worklist.truncate (0);
2072 27726441 : m_wl_ix = 0;
2073 27726441 : m_lhs_search.clear_search ();
2074 27726441 : 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 27726441 : relation_kind rel = recomputed_relation (bb, lhs, rhs);
2082 :
2083 27726441 : if (rel != VREL_VARYING)
2084 : {
2085 144814 : rel = relation_intersect (result, rel);
2086 144814 : if (rel != VREL_UNDEFINED)
2087 144814 : 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 27726441 : cache_relation (bb, result, lhs, rhs);
2093 :
2094 27726441 : 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 27726441 : 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 121062121 : dom_oracle::query (basic_block bb, tree ssa1, tree ssa2)
2112 : {
2113 121062121 : relation_kind kind;
2114 121062121 : unsigned v1 = SSA_NAME_VERSION (ssa1);
2115 121062121 : unsigned v2 = SSA_NAME_VERSION (ssa2);
2116 121062121 : 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 203336271 : if ((!bitmap_bit_p (m_relation_set, v1) && !has_equiv_p (v1))
2122 124718314 : || (!bitmap_bit_p (m_relation_set, v2) && !has_equiv_p (v2)))
2123 93083752 : return partial_equiv (ssa1, ssa2);
2124 :
2125 : // Check for equivalence first. They must be in each equivalency set.
2126 27876586 : const_bitmap equiv1 = equiv_set (ssa1, bb);
2127 27876586 : const_bitmap equiv2 = equiv_set (ssa2, bb);
2128 27876586 : 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 27726441 : kind = relation_search (bb, ssa1, equiv1, ssa2, equiv2);
2135 :
2136 : // Finally look for partial equivalences.
2137 27726441 : if (kind == VREL_VARYING)
2138 16318262 : 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 9400721 : path_oracle::path_oracle (relation_oracle *oracle)
2184 : {
2185 9400721 : set_root_oracle (oracle);
2186 9400721 : bitmap_obstack_initialize (&m_bitmaps);
2187 9400721 : obstack_init (&m_chain_obstack);
2188 :
2189 : // Initialize header records.
2190 9400721 : m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
2191 9400721 : m_equiv.m_bb = NULL;
2192 9400721 : m_equiv.m_next = NULL;
2193 9400721 : m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
2194 9400721 : m_relations.m_head = NULL;
2195 9400721 : m_killed_defs = BITMAP_ALLOC (&m_bitmaps);
2196 9400721 : }
2197 :
2198 18801442 : path_oracle::~path_oracle ()
2199 : {
2200 9400721 : obstack_free (&m_chain_obstack, NULL);
2201 9400721 : bitmap_obstack_release (&m_bitmaps);
2202 18801442 : }
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 144242341 : path_oracle::equiv_set (tree ssa, basic_block bb)
2225 : {
2226 : // Check the list first.
2227 144242341 : equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
2228 144242341 : if (ptr)
2229 77335320 : return ptr->m_names;
2230 :
2231 : // Otherwise defer to the root oracle.
2232 66907021 : if (m_root)
2233 60499689 : return m_root->equiv_set (ssa, bb);
2234 :
2235 : // Allocate a throw away bitmap if there isn't a root oracle.
2236 6407332 : bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
2237 6407332 : bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
2238 6407332 : 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 8794497 : path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
2246 : {
2247 8794497 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
2248 8794497 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
2249 :
2250 : // Check if they are the same set, if so, we're done.
2251 8794497 : 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 8773890 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
2256 8773890 : valid_equivs (b, equiv_1, bb);
2257 8773890 : valid_equivs (b, equiv_2, bb);
2258 :
2259 8773890 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
2260 : sizeof (equiv_chain));
2261 8773890 : ptr->m_names = b;
2262 8773890 : ptr->m_bb = NULL;
2263 8773890 : ptr->m_next = m_equiv.m_next;
2264 8773890 : m_equiv.m_next = ptr;
2265 8773890 : bitmap_ior_into (m_equiv.m_names, b);
2266 8773890 : return true;
2267 : }
2268 :
2269 : // Register killing definition of an SSA_NAME.
2270 :
2271 : void
2272 62351886 : path_oracle::killing_def (tree ssa)
2273 : {
2274 62351886 : 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 62351886 : unsigned v = SSA_NAME_VERSION (ssa);
2282 :
2283 62351886 : bitmap_set_bit (m_killed_defs, v);
2284 62351886 : 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 62351886 : bitmap b = BITMAP_ALLOC (&m_bitmaps);
2288 62351886 : bitmap_set_bit (b, v);
2289 62351886 : equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
2290 : sizeof (equiv_chain));
2291 62351886 : ptr->m_names = b;
2292 62351886 : ptr->m_bb = NULL;
2293 62351886 : ptr->m_next = m_equiv.m_next;
2294 62351886 : m_equiv.m_next = ptr;
2295 :
2296 : // Walk the relation list and remove SSA from any relations.
2297 62351886 : if (!bitmap_bit_p (m_relations.m_names, v))
2298 : return;
2299 :
2300 411971 : bitmap_clear_bit (m_relations.m_names, v);
2301 411971 : relation_chain **prev = &(m_relations.m_head);
2302 411971 : relation_chain *next = NULL;
2303 943995 : for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
2304 : {
2305 532024 : gcc_checking_assert (*prev == ptr);
2306 532024 : next = ptr->m_next;
2307 532024 : if (SSA_NAME_VERSION (ptr->op1 ()) == v
2308 532024 : || SSA_NAME_VERSION (ptr->op2 ()) == v)
2309 340437 : *prev = ptr->m_next;
2310 : else
2311 191587 : 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 32829044 : 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 32829044 : 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 32783915 : if (relation_partial_equiv_p (k))
2330 : return false;
2331 :
2332 28957377 : 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 28957377 : if (curr != VREL_VARYING && !relation_partial_equiv_p (curr))
2336 4529840 : k = relation_intersect (curr, k);
2337 :
2338 : // Do not register an impossible relation.
2339 28957377 : if (k == VREL_UNDEFINED)
2340 : return false;
2341 :
2342 26657769 : bool ret;
2343 26657769 : if (k == VREL_EQ)
2344 8794497 : ret = register_equiv (bb, ssa1, ssa2);
2345 : else
2346 : {
2347 17863272 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
2348 17863272 : bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
2349 17863272 : relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
2350 : sizeof (relation_chain));
2351 17863272 : ptr->set_relation (k, ssa1, ssa2);
2352 17863272 : ptr->m_next = m_relations.m_head;
2353 17863272 : m_relations.m_head = ptr;
2354 17863272 : ret = true;
2355 : }
2356 :
2357 26657769 : 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 53341186 : path_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2)
2372 : {
2373 53341186 : if (bitmap_equal_p (b1, b2))
2374 : return VREL_EQ;
2375 :
2376 53341186 : 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 53341186 : if (bitmap_intersect_p (m_killed_defs, b1)
2381 53341186 : || bitmap_intersect_p (m_killed_defs, b2))
2382 : return k;
2383 :
2384 : // Query the root oracle for relations with path local equivalencies.
2385 14640921 : if (k == VREL_VARYING && m_root)
2386 12109701 : 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 54015977 : path_oracle::query (basic_block bb, tree ssa1, tree ssa2)
2396 : {
2397 54015977 : unsigned v1 = SSA_NAME_VERSION (ssa1);
2398 54015977 : unsigned v2 = SSA_NAME_VERSION (ssa2);
2399 :
2400 54015977 : if (v1 == v2)
2401 : return VREL_EQ;
2402 :
2403 53921741 : const_bitmap equiv_1 = equiv_set (ssa1, bb);
2404 53921741 : const_bitmap equiv_2 = equiv_set (ssa2, bb);
2405 53921741 : if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
2406 : return VREL_EQ;
2407 :
2408 53341186 : 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 53341186 : if (rel == VREL_VARYING && m_root)
2412 46242710 : 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 40108582 : path_oracle::reset_path (relation_oracle *oracle)
2421 : {
2422 40108582 : set_root_oracle (oracle);
2423 40108582 : m_equiv.m_next = NULL;
2424 40108582 : bitmap_clear (m_equiv.m_names);
2425 40108582 : m_relations.m_head = NULL;
2426 40108582 : bitmap_clear (m_relations.m_names);
2427 40108582 : bitmap_clear (m_killed_defs);
2428 40108582 : }
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 55968172 : equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle,
2466 : basic_block bb, tree name,
2467 : bool full, bool partial)
2468 : {
2469 55968172 : m_name = name;
2470 55968172 : m_oracle = oracle;
2471 55968172 : m_pe = partial ? oracle->partial_equiv_set (name) : NULL;
2472 55968172 : m_bm = NULL;
2473 55968172 : if (full)
2474 55968172 : m_bm = oracle->equiv_set (name, bb);
2475 55968172 : if (!m_bm && m_pe)
2476 0 : m_bm = m_pe->members;
2477 55968172 : if (m_bm)
2478 55968171 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
2479 55968172 : }
2480 :
2481 : // Move to the next export bitmap spot.
2482 :
2483 : void
2484 73988935 : equiv_relation_iterator::next ()
2485 : {
2486 73988935 : bmp_iter_next (&m_bi, &m_y);
2487 73988935 : }
2488 :
2489 : // Fetch the name of the next export in the export list. Return NULL if
2490 : // iteration is done.
2491 :
2492 : tree
2493 67337856 : equiv_relation_iterator::get_name (relation_kind *rel)
2494 : {
2495 73988778 : if (!m_bm)
2496 : return NULL_TREE;
2497 :
2498 136608028 : while (bmp_iter_set (&m_bi, &m_y))
2499 : {
2500 : // Do not return self.
2501 73988935 : tree t = ssa_name (m_y);
2502 73988935 : if (t && t != m_name)
2503 : {
2504 11369700 : relation_kind k = VREL_EQ;
2505 11369700 : if (m_pe && m_bm == m_pe->members)
2506 : {
2507 8507063 : const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t);
2508 8507063 : if (equiv_pe && equiv_pe->members == m_pe->members)
2509 8507047 : k = pe_min (m_pe->code, equiv_pe->code);
2510 : else
2511 : k = VREL_VARYING;
2512 : }
2513 8507063 : if (relation_equiv_p (k))
2514 : {
2515 11369684 : if (rel)
2516 11369684 : *rel = k;
2517 : return t;
2518 : }
2519 : }
2520 62619251 : next ();
2521 : }
2522 :
2523 : // Process partial equivs after full equivs if both were requested.
2524 62619093 : if (m_pe && m_bm != m_pe->members)
2525 : {
2526 55968171 : m_bm = m_pe->members;
2527 55968171 : if (m_bm)
2528 : {
2529 : // Recursively call back to process First PE.
2530 6650922 : bmp_iter_set_init (&m_bi, m_bm, 1, &m_y);
2531 6650922 : 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
|