1 /* Header file for the value range relational processing.
2 Copyright (C) 2020-2022 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 // These VREL codes are arranged such that VREL_NONE is the first
36 // code, and all the rest are contiguous up to and including VREL_LAST.
37
38 #define VREL_FIRST VREL_NONE
39 #define VREL_LAST NE_EXPR
40 #define VREL_COUNT (VREL_LAST - VREL_FIRST + 1)
41
42 // vrel_range_assert will either assert that the tree code passed is valid,
43 // or mark invalid codes as unreachable to help with table optimation.
44 #if CHECKING_P
45 #define vrel_range_assert(c) \
46 gcc_checking_assert ((c) >= VREL_FIRST && (c) <= VREL_LAST)
47 #else
48 #define vrel_range_assert(c) \
49 if ((c) < VREL_FIRST || (c) > VREL_LAST) \
50 gcc_unreachable ();
51 #endif
52
53 static const char *kind_string[VREL_COUNT] =
54 { "none", "<", "<=", ">", ">=", "empty", "==", "!=" };
55
56 // Print a relation_kind REL to file F.
57
58 void
print_relation(FILE * f,relation_kind rel)59 print_relation (FILE *f, relation_kind rel)
60 {
61 vrel_range_assert (rel);
62 fprintf (f, " %s ", kind_string[rel - VREL_FIRST]);
63 }
64
65 // This table is used to negate the operands. op1 REL op2 -> !(op1 REL op2).
66 relation_kind rr_negate_table[VREL_COUNT] = {
67 // NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR
68 VREL_NONE, GE_EXPR, GT_EXPR, LE_EXPR, LT_EXPR, VREL_EMPTY, NE_EXPR, EQ_EXPR };
69
70 // Negate the relation, as in logical negation.
71
72 relation_kind
relation_negate(relation_kind r)73 relation_negate (relation_kind r)
74 {
75 vrel_range_assert (r);
76 return rr_negate_table [r - VREL_FIRST];
77 }
78
79 // This table is used to swap the operands. op1 REL op2 -> op2 REL op1.
80 relation_kind rr_swap_table[VREL_COUNT] = {
81 // NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR
82 VREL_NONE, GT_EXPR, GE_EXPR, LT_EXPR, LE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR };
83
84 // Return the relation as if the operands were swapped.
85
86 relation_kind
relation_swap(relation_kind r)87 relation_swap (relation_kind r)
88 {
89 vrel_range_assert (r);
90 return rr_swap_table [r - VREL_FIRST];
91 }
92
93 // This table is used to perform an intersection between 2 relations.
94
95 relation_kind rr_intersect_table[VREL_COUNT][VREL_COUNT] = {
96 // NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR
97 // VREL_NONE
98 { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR },
99 // LT_EXPR
100 { LT_EXPR, LT_EXPR, LT_EXPR, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, LT_EXPR },
101 // LE_EXPR
102 { LE_EXPR, LT_EXPR, LE_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, LT_EXPR },
103 // GT_EXPR
104 { GT_EXPR, VREL_EMPTY, VREL_EMPTY, GT_EXPR, GT_EXPR, VREL_EMPTY, VREL_EMPTY, GT_EXPR },
105 // GE_EXPR
106 { GE_EXPR, VREL_EMPTY, EQ_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, GT_EXPR },
107 // VREL_EMPTY
108 { VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY, VREL_EMPTY },
109 // EQ_EXPR
110 { EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY, EQ_EXPR, VREL_EMPTY },
111 // NE_EXPR
112 { NE_EXPR, LT_EXPR, LT_EXPR, GT_EXPR, GT_EXPR, VREL_EMPTY, VREL_EMPTY, NE_EXPR } };
113
114
115 // Intersect relation R1 with relation R2 and return the resulting relation.
116
117 relation_kind
relation_intersect(relation_kind r1,relation_kind r2)118 relation_intersect (relation_kind r1, relation_kind r2)
119 {
120 vrel_range_assert (r1);
121 vrel_range_assert (r2);
122 return rr_intersect_table[r1 - VREL_FIRST][r2 - VREL_FIRST];
123 }
124
125
126 // This table is used to perform a union between 2 relations.
127
128 relation_kind rr_union_table[VREL_COUNT][VREL_COUNT] = {
129 // NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR
130 // VREL_NONE
131 { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE },
132 // LT_EXPR
133 { VREL_NONE, LT_EXPR, LE_EXPR, NE_EXPR, VREL_NONE, LT_EXPR, LE_EXPR, NE_EXPR },
134 // LE_EXPR
135 { VREL_NONE, LE_EXPR, LE_EXPR, VREL_NONE, VREL_NONE, LE_EXPR, LE_EXPR, VREL_NONE },
136 // GT_EXPR
137 { VREL_NONE, NE_EXPR, VREL_NONE, GT_EXPR, GE_EXPR, GT_EXPR, GE_EXPR, NE_EXPR },
138 // GE_EXPR
139 { VREL_NONE, VREL_NONE, VREL_NONE, GE_EXPR, GE_EXPR, GE_EXPR, GE_EXPR, VREL_NONE },
140 // VREL_EMPTY
141 { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_EMPTY, EQ_EXPR, NE_EXPR },
142 // EQ_EXPR
143 { VREL_NONE, LE_EXPR, LE_EXPR, GE_EXPR, GE_EXPR, EQ_EXPR, EQ_EXPR, VREL_NONE },
144 // NE_EXPR
145 { VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR, VREL_NONE, NE_EXPR } };
146
147 // Union relation R1 with relation R2 and return the result.
148
149 relation_kind
relation_union(relation_kind r1,relation_kind r2)150 relation_union (relation_kind r1, relation_kind r2)
151 {
152 vrel_range_assert (r1);
153 vrel_range_assert (r2);
154 return rr_union_table[r1 - VREL_FIRST][r2 - VREL_FIRST];
155 }
156
157
158 // This table is used to determine transitivity between 2 relations.
159 // (A relation0 B) and (B relation1 C) implies (A result C)
160
161 relation_kind rr_transitive_table[VREL_COUNT][VREL_COUNT] = {
162 // NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EMPTY, EQ_EXPR, NE_EXPR
163 // VREL_NONE
164 { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE },
165 // LT_EXPR
166 { VREL_NONE, LT_EXPR, LT_EXPR, VREL_NONE, VREL_NONE, VREL_NONE, LT_EXPR, VREL_NONE },
167 // LE_EXPR
168 { VREL_NONE, LT_EXPR, LE_EXPR, VREL_NONE, VREL_NONE, VREL_NONE, LE_EXPR, VREL_NONE },
169 // GT_EXPR
170 { VREL_NONE, VREL_NONE, VREL_NONE, GT_EXPR, GT_EXPR, VREL_NONE, GT_EXPR, VREL_NONE },
171 // GE_EXPR
172 { VREL_NONE, VREL_NONE, VREL_NONE, GT_EXPR, GE_EXPR, VREL_NONE, GE_EXPR, VREL_NONE },
173 // VREL_EMPTY
174 { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE },
175 // EQ_EXPR
176 { VREL_NONE, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, VREL_NONE, EQ_EXPR, VREL_NONE },
177 // NE_EXPR
178 { VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE, VREL_NONE } };
179
180 // Apply transitive operation between relation R1 and relation R2, and
181 // return the resulting relation, if any.
182
183 relation_kind
relation_transitive(relation_kind r1,relation_kind r2)184 relation_transitive (relation_kind r1, relation_kind r2)
185 {
186 vrel_range_assert (r1);
187 vrel_range_assert (r2);
188 return rr_transitive_table[r1 - VREL_FIRST][r2 - VREL_FIRST];
189 }
190
191 // Given an equivalence set EQUIV, set all the bits in B that are still valid
192 // members of EQUIV in basic block BB.
193
194 void
valid_equivs(bitmap b,const_bitmap equivs,basic_block bb)195 relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb)
196 {
197 unsigned i;
198 bitmap_iterator bi;
199 EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
200 {
201 tree ssa = ssa_name (i);
202 const_bitmap ssa_equiv = equiv_set (ssa, bb);
203 if (ssa_equiv == equivs)
204 bitmap_set_bit (b, i);
205 }
206 }
207
208 // -------------------------------------------------------------------------
209
210 // The very first element in the m_equiv chain is actually just a summary
211 // element in which the m_names bitmap is used to indicate that an ssa_name
212 // has an equivalence set in this block.
213 // This allows for much faster traversal of the DOM chain, as a search for
214 // SSA_NAME simply requires walking the DOM chain until a block is found
215 // which has the bit for SSA_NAME set. Then scan for the equivalency set in
216 // that block. No previous lists need be searched.
217
218 // If SSA has an equivalence in this list, find and return it.
219 // Otherwise return NULL.
220
221 equiv_chain *
find(unsigned ssa)222 equiv_chain::find (unsigned ssa)
223 {
224 equiv_chain *ptr = NULL;
225 // If there are equiv sets and SSA is in one in this list, find it.
226 // Otherwise return NULL.
227 if (bitmap_bit_p (m_names, ssa))
228 {
229 for (ptr = m_next; ptr; ptr = ptr->m_next)
230 if (bitmap_bit_p (ptr->m_names, ssa))
231 break;
232 }
233 return ptr;
234 }
235
236 // Dump the names in this equivalence set.
237
238 void
dump(FILE * f) const239 equiv_chain::dump (FILE *f) const
240 {
241 bitmap_iterator bi;
242 unsigned i;
243
244 if (!m_names)
245 return;
246 fprintf (f, "Equivalence set : [");
247 unsigned c = 0;
248 EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi)
249 {
250 if (ssa_name (i))
251 {
252 if (c++)
253 fprintf (f, ", ");
254 print_generic_expr (f, ssa_name (i), TDF_SLIM);
255 }
256 }
257 fprintf (f, "]\n");
258 }
259
260 // Instantiate an equivalency oracle.
261
equiv_oracle()262 equiv_oracle::equiv_oracle ()
263 {
264 bitmap_obstack_initialize (&m_bitmaps);
265 m_equiv.create (0);
266 m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
267 m_equiv_set = BITMAP_ALLOC (&m_bitmaps);
268 obstack_init (&m_chain_obstack);
269 m_self_equiv.create (0);
270 m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
271 }
272
273 // Destruct an equivalency oracle.
274
~equiv_oracle()275 equiv_oracle::~equiv_oracle ()
276 {
277 m_self_equiv.release ();
278 obstack_free (&m_chain_obstack, NULL);
279 m_equiv.release ();
280 bitmap_obstack_release (&m_bitmaps);
281 }
282
283 // Find and return the equivalency set for SSA along the dominators of BB.
284 // This is the external API.
285
286 const_bitmap
equiv_set(tree ssa,basic_block bb)287 equiv_oracle::equiv_set (tree ssa, basic_block bb)
288 {
289 // Search the dominator tree for an equivalency.
290 equiv_chain *equiv = find_equiv_dom (ssa, bb);
291 if (equiv)
292 return equiv->m_names;
293
294 // Otherwise return a cached equiv set containing just this SSA.
295 unsigned v = SSA_NAME_VERSION (ssa);
296 if (v >= m_self_equiv.length ())
297 m_self_equiv.safe_grow_cleared (num_ssa_names + 1);
298
299 if (!m_self_equiv[v])
300 {
301 m_self_equiv[v] = BITMAP_ALLOC (&m_bitmaps);
302 bitmap_set_bit (m_self_equiv[v], v);
303 }
304 return m_self_equiv[v];
305 }
306
307 // Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
308
309 relation_kind
query_relation(basic_block bb,tree ssa1,tree ssa2)310 equiv_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
311 {
312 // If the 2 ssa names share the same equiv set, they are equal.
313 if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb))
314 return EQ_EXPR;
315 return VREL_NONE;
316 }
317
318 // Query if thre is a relation (equivalence) between 2 SSA_NAMEs.
319
320 relation_kind
query_relation(basic_block bb ATTRIBUTE_UNUSED,const_bitmap e1,const_bitmap e2)321 equiv_oracle::query_relation (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1,
322 const_bitmap e2)
323 {
324 // If the 2 ssa names share the same equiv set, they are equal.
325 if (bitmap_equal_p (e1, e2))
326 return EQ_EXPR;
327 return VREL_NONE;
328 }
329
330 // If SSA has an equivalence in block BB, find and return it.
331 // Otherwise return NULL.
332
333 equiv_chain *
find_equiv_block(unsigned ssa,int bb) const334 equiv_oracle::find_equiv_block (unsigned ssa, int bb) const
335 {
336 if (bb >= (int)m_equiv.length () || !m_equiv[bb])
337 return NULL;
338
339 return m_equiv[bb]->find (ssa);
340 }
341
342 // Starting at block BB, walk the dominator chain looking for the nearest
343 // equivalence set containing NAME.
344
345 equiv_chain *
find_equiv_dom(tree name,basic_block bb) const346 equiv_oracle::find_equiv_dom (tree name, basic_block bb) const
347 {
348 unsigned v = SSA_NAME_VERSION (name);
349 // Short circuit looking for names which have no equivalences.
350 // Saves time looking for something which does not exist.
351 if (!bitmap_bit_p (m_equiv_set, v))
352 return NULL;
353
354 // NAME has at least once equivalence set, check to see if it has one along
355 // the dominator tree.
356 for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
357 {
358 equiv_chain *ptr = find_equiv_block (v, bb->index);
359 if (ptr)
360 return ptr;
361 }
362 return NULL;
363 }
364
365 // Register equivalance between ssa_name V and set EQUIV in block BB,
366
367 bitmap
register_equiv(basic_block bb,unsigned v,equiv_chain * equiv)368 equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv)
369 {
370 // V will have an equivalency now.
371 bitmap_set_bit (m_equiv_set, v);
372
373 // If that equiv chain is in this block, simply use it.
374 if (equiv->m_bb == bb)
375 {
376 bitmap_set_bit (equiv->m_names, v);
377 bitmap_set_bit (m_equiv[bb->index]->m_names, v);
378 return NULL;
379 }
380
381 // Otherwise create an equivalence for this block which is a copy
382 // of equiv, the add V to the set.
383 bitmap b = BITMAP_ALLOC (&m_bitmaps);
384 valid_equivs (b, equiv->m_names, bb);
385 bitmap_set_bit (b, v);
386 return b;
387 }
388
389 // Register equivalence between set equiv_1 and equiv_2 in block BB.
390 // Return NULL if either name can be merged with the other. Otherwise
391 // return a pointer to the combined bitmap of names. This allows the
392 // caller to do any setup required for a new element.
393
394 bitmap
register_equiv(basic_block bb,equiv_chain * equiv_1,equiv_chain * equiv_2)395 equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1,
396 equiv_chain *equiv_2)
397 {
398 // If equiv_1 is already in BB, use it as the combined set.
399 if (equiv_1->m_bb == bb)
400 {
401 valid_equivs (equiv_1->m_names, equiv_2->m_names, bb);
402 // Its hard to delete from a single linked list, so
403 // just clear the second one.
404 if (equiv_2->m_bb == bb)
405 bitmap_clear (equiv_2->m_names);
406 else
407 // Ensure the new names are in the summary for BB.
408 bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names);
409 return NULL;
410 }
411 // If equiv_2 is in BB, use it for the combined set.
412 if (equiv_2->m_bb == bb)
413 {
414 valid_equivs (equiv_2->m_names, equiv_1->m_names, bb);
415 // Ensure the new names are in the summary.
416 bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names);
417 return NULL;
418 }
419
420 // At this point, neither equivalence is from this block.
421 bitmap b = BITMAP_ALLOC (&m_bitmaps);
422 valid_equivs (b, equiv_1->m_names, bb);
423 valid_equivs (b, equiv_2->m_names, bb);
424 return b;
425 }
426
427 // Create an equivalency set containing only SSA in its definition block.
428 // This is done the first time SSA is registered in an equivalency and blocks
429 // any DOM searches past the definition.
430
431 void
register_initial_def(tree ssa)432 equiv_oracle::register_initial_def (tree ssa)
433 {
434 if (SSA_NAME_IS_DEFAULT_DEF (ssa))
435 return;
436 basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa));
437 gcc_checking_assert (bb && !find_equiv_dom (ssa, bb));
438
439 unsigned v = SSA_NAME_VERSION (ssa);
440 bitmap_set_bit (m_equiv_set, v);
441 bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps);
442 bitmap_set_bit (equiv_set, v);
443 add_equiv_to_block (bb, equiv_set);
444 }
445
446 // Register an equivalence between SSA1 and SSA2 in block BB.
447 // The equivalence oracle maintains a vector of equivalencies indexed by basic
448 // block. When an equivalence bteween SSA1 and SSA2 is registered in block BB,
449 // a query is made as to what equivalences both names have already, and
450 // any preexisting equivalences are merged to create a single equivalence
451 // containing all the ssa_names in this basic block.
452
453 void
register_relation(basic_block bb,relation_kind k,tree ssa1,tree ssa2)454 equiv_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
455 tree ssa2)
456 {
457 // Only handle equality relations.
458 if (k != EQ_EXPR)
459 return;
460
461 unsigned v1 = SSA_NAME_VERSION (ssa1);
462 unsigned v2 = SSA_NAME_VERSION (ssa2);
463
464 // If this is the first time an ssa_name has an equivalency registered
465 // create a self-equivalency record in the def block.
466 if (!bitmap_bit_p (m_equiv_set, v1))
467 register_initial_def (ssa1);
468 if (!bitmap_bit_p (m_equiv_set, v2))
469 register_initial_def (ssa2);
470
471 equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb);
472 equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb);
473
474 // Check if they are the same set
475 if (equiv_1 && equiv_1 == equiv_2)
476 return;
477
478 bitmap equiv_set;
479
480 // Case where we have 2 SSA_NAMEs that are not in any set.
481 if (!equiv_1 && !equiv_2)
482 {
483 bitmap_set_bit (m_equiv_set, v1);
484 bitmap_set_bit (m_equiv_set, v2);
485
486 equiv_set = BITMAP_ALLOC (&m_bitmaps);
487 bitmap_set_bit (equiv_set, v1);
488 bitmap_set_bit (equiv_set, v2);
489 }
490 else if (!equiv_1 && equiv_2)
491 equiv_set = register_equiv (bb, v1, equiv_2);
492 else if (equiv_1 && !equiv_2)
493 equiv_set = register_equiv (bb, v2, equiv_1);
494 else
495 equiv_set = register_equiv (bb, equiv_1, equiv_2);
496
497 // A non-null return is a bitmap that is to be added to the current
498 // block as a new equivalence.
499 if (!equiv_set)
500 return;
501
502 add_equiv_to_block (bb, equiv_set);
503 }
504
505 // Add an equivalency record in block BB containing bitmap EQUIV_SET.
506 // Note the internal caller is responible for allocating EQUIV_SET properly.
507
508 void
add_equiv_to_block(basic_block bb,bitmap equiv_set)509 equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set)
510 {
511 equiv_chain *ptr;
512
513 // Check if this is the first time a block has an equivalence added.
514 // and create a header block. And set the summary for this block.
515 if (!m_equiv[bb->index])
516 {
517 ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
518 sizeof (equiv_chain));
519 ptr->m_names = BITMAP_ALLOC (&m_bitmaps);
520 bitmap_copy (ptr->m_names, equiv_set);
521 ptr->m_bb = bb;
522 ptr->m_next = NULL;
523 m_equiv[bb->index] = ptr;
524 }
525
526 // Now create the element for this equiv set and initialize it.
527 ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain));
528 ptr->m_names = equiv_set;
529 ptr->m_bb = bb;
530 gcc_checking_assert (bb->index < (int)m_equiv.length ());
531 ptr->m_next = m_equiv[bb->index]->m_next;
532 m_equiv[bb->index]->m_next = ptr;
533 bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set);
534 }
535
536 // Make sure the BB vector is big enough and grow it if needed.
537
538 void
limit_check(basic_block bb)539 equiv_oracle::limit_check (basic_block bb)
540 {
541 int i = (bb) ? bb->index : last_basic_block_for_fn (cfun);
542 if (i >= (int)m_equiv.length ())
543 m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
544 }
545
546 // Dump the equivalence sets in BB to file F.
547
548 void
dump(FILE * f,basic_block bb) const549 equiv_oracle::dump (FILE *f, basic_block bb) const
550 {
551 if (bb->index >= (int)m_equiv.length ())
552 return;
553 if (!m_equiv[bb->index])
554 return;
555
556 equiv_chain *ptr = m_equiv[bb->index]->m_next;
557 for (; ptr; ptr = ptr->m_next)
558 ptr->dump (f);
559 }
560
561 // Dump all equivalence sets known to the oracle.
562
563 void
dump(FILE * f) const564 equiv_oracle::dump (FILE *f) const
565 {
566 fprintf (f, "Equivalency dump\n");
567 for (unsigned i = 0; i < m_equiv.length (); i++)
568 if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i))
569 {
570 fprintf (f, "BB%d\n", i);
571 dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
572 }
573 }
574
575
576 // --------------------------------------------------------------------------
577
578 // The value-relation class is used to encapsulate the represention of an
579 // individual relation between 2 ssa-names, and to facilitate operating on
580 // the relation.
581
582 class value_relation
583 {
584 public:
585 value_relation ();
586 value_relation (relation_kind kind, tree n1, tree n2);
587 void set_relation (relation_kind kind, tree n1, tree n2);
588
kind() const589 inline relation_kind kind () const { return related; }
op1() const590 inline tree op1 () const { return name1; }
op2() const591 inline tree op2 () const { return name2; }
592
593 bool union_ (value_relation &p);
594 bool intersect (value_relation &p);
595 void negate ();
596 bool apply_transitive (const value_relation &rel);
597
598 void dump (FILE *f) const;
599 private:
600 relation_kind related;
601 tree name1, name2;
602 };
603
604 // Set relation R between ssa_name N1 and N2.
605
606 inline void
set_relation(relation_kind r,tree n1,tree n2)607 value_relation::set_relation (relation_kind r, tree n1, tree n2)
608 {
609 gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2));
610 related = r;
611 name1 = n1;
612 name2 = n2;
613 }
614
615 // Default constructor.
616
617 inline
value_relation()618 value_relation::value_relation ()
619 {
620 related = VREL_NONE;
621 name1 = NULL_TREE;
622 name2 = NULL_TREE;
623 }
624
625 // Constructor for relation R between SSA version N1 nd N2.
626
627 inline
value_relation(relation_kind kind,tree n1,tree n2)628 value_relation::value_relation (relation_kind kind, tree n1, tree n2)
629 {
630 set_relation (kind, n1, n2);
631 }
632
633 // Negate the current relation.
634
635 void
negate()636 value_relation::negate ()
637 {
638 related = relation_negate (related);
639 }
640
641 // Perform an intersection between 2 relations. *this &&= p.
642
643 bool
intersect(value_relation & p)644 value_relation::intersect (value_relation &p)
645 {
646 // Save previous value
647 relation_kind old = related;
648
649 if (p.op1 () == op1 () && p.op2 () == op2 ())
650 related = relation_intersect (kind (), p.kind ());
651 else if (p.op2 () == op1 () && p.op1 () == op2 ())
652 related = relation_intersect (kind (), relation_swap (p.kind ()));
653 else
654 return false;
655
656 return old != related;
657 }
658
659 // Perform a union between 2 relations. *this ||= p.
660
661 bool
union_(value_relation & p)662 value_relation::union_ (value_relation &p)
663 {
664 // Save previous value
665 relation_kind old = related;
666
667 if (p.op1 () == op1 () && p.op2 () == op2 ())
668 related = relation_union (kind(), p.kind());
669 else if (p.op2 () == op1 () && p.op1 () == op2 ())
670 related = relation_union (kind(), relation_swap (p.kind ()));
671 else
672 return false;
673
674 return old != related;
675 }
676
677 // Identify and apply any transitive relations between REL
678 // and THIS. Return true if there was a transformation.
679
680 bool
apply_transitive(const value_relation & rel)681 value_relation::apply_transitive (const value_relation &rel)
682 {
683 relation_kind k = VREL_NONE;
684
685 // Idenity any common operand, and notrmalize the relations to
686 // the form : A < B B < C produces A < C
687 if (rel.op1 () == name2)
688 {
689 // A < B B < C
690 if (rel.op2 () == name1)
691 return false;
692 k = relation_transitive (kind (), rel.kind ());
693 if (k != VREL_NONE)
694 {
695 related = k;
696 name2 = rel.op2 ();
697 return true;
698 }
699 }
700 else if (rel.op1 () == name1)
701 {
702 // B > A B < C
703 if (rel.op2 () == name2)
704 return false;
705 k = relation_transitive (relation_swap (kind ()), rel.kind ());
706 if (k != VREL_NONE)
707 {
708 related = k;
709 name1 = name2;
710 name2 = rel.op2 ();
711 return true;
712 }
713 }
714 else if (rel.op2 () == name2)
715 {
716 // A < B C > B
717 if (rel.op1 () == name1)
718 return false;
719 k = relation_transitive (kind (), relation_swap (rel.kind ()));
720 if (k != VREL_NONE)
721 {
722 related = k;
723 name2 = rel.op1 ();
724 return true;
725 }
726 }
727 else if (rel.op2 () == name1)
728 {
729 // B > A C > B
730 if (rel.op1 () == name2)
731 return false;
732 k = relation_transitive (relation_swap (kind ()),
733 relation_swap (rel.kind ()));
734 if (k != VREL_NONE)
735 {
736 related = k;
737 name1 = name2;
738 name2 = rel.op1 ();
739 return true;
740 }
741 }
742 return false;
743 }
744
745 // Dump the relation to file F.
746
747 void
dump(FILE * f) const748 value_relation::dump (FILE *f) const
749 {
750 if (!name1 || !name2)
751 {
752 fprintf (f, "uninitialized");
753 return;
754 }
755 fputc ('(', f);
756 print_generic_expr (f, op1 (), TDF_SLIM);
757 print_relation (f, kind ());
758 print_generic_expr (f, op2 (), TDF_SLIM);
759 fputc(')', f);
760 }
761
762 // This container is used to link relations in a chain.
763
764 class relation_chain : public value_relation
765 {
766 public:
767 relation_chain *m_next;
768 };
769
770 // ------------------------------------------------------------------------
771
772 // Find the relation between any ssa_name in B1 and any name in B2 in LIST.
773 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
774
775 relation_kind
find_relation(const_bitmap b1,const_bitmap b2) const776 relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const
777 {
778 if (!m_names)
779 return VREL_NONE;
780
781 // If both b1 and b2 aren't referenced in thie block, cant be a relation
782 if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2))
783 return VREL_NONE;
784
785 // Search for the fiorst relation that contains BOTH an element from B1
786 // and B2, and return that relation.
787 for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next)
788 {
789 unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
790 unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
791 if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2))
792 return ptr->kind ();
793 if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1))
794 return relation_swap (ptr->kind ());
795 }
796
797 return VREL_NONE;
798 }
799
800 // Instantiate a relation oracle.
801
dom_oracle()802 dom_oracle::dom_oracle ()
803 {
804 m_relations.create (0);
805 m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
806 m_relation_set = BITMAP_ALLOC (&m_bitmaps);
807 m_tmp = BITMAP_ALLOC (&m_bitmaps);
808 m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
809 }
810
811 // Destruct a relation oracle.
812
~dom_oracle()813 dom_oracle::~dom_oracle ()
814 {
815 m_relations.release ();
816 }
817
818 // Register relation K between ssa_name OP1 and OP2 on STMT.
819
820 void
register_stmt(gimple * stmt,relation_kind k,tree op1,tree op2)821 relation_oracle::register_stmt (gimple *stmt, relation_kind k, tree op1,
822 tree op2)
823 {
824 gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
825 gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
826 gcc_checking_assert (stmt && gimple_bb (stmt));
827
828 // Don't register lack of a relation.
829 if (k == VREL_NONE)
830 return;
831
832 if (dump_file && (dump_flags & TDF_DETAILS))
833 {
834 value_relation vr (k, op1, op2);
835 fprintf (dump_file, " Registering value_relation ");
836 vr.dump (dump_file);
837 fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index);
838 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
839 }
840
841 // If an equivalence is being added between a PHI and one of its arguments
842 // make sure that that argument is not defined in the same block.
843 // This can happen along back edges and the equivalence will not be
844 // applicable as it would require a use before def.
845 if (k == EQ_EXPR && is_a<gphi *> (stmt))
846 {
847 tree phi_def = gimple_phi_result (stmt);
848 gcc_checking_assert (phi_def == op1 || phi_def == op2);
849 tree arg = op2;
850 if (phi_def == op2)
851 arg = op1;
852 if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg)))
853 {
854 if (dump_file && (dump_flags & TDF_DETAILS))
855 {
856 fprintf (dump_file, " Not registered due to ");
857 print_generic_expr (dump_file, arg, TDF_SLIM);
858 fprintf (dump_file, " being defined in the same block.\n");
859 }
860 return;
861 }
862 }
863 register_relation (gimple_bb (stmt), k, op1, op2);
864 }
865
866 // Register relation K between ssa_name OP1 and OP2 on edge E.
867
868 void
register_edge(edge e,relation_kind k,tree op1,tree op2)869 relation_oracle::register_edge (edge e, relation_kind k, tree op1, tree op2)
870 {
871 gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
872 gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
873
874 // Do not register lack of relation, or blocks which have more than
875 // edge E for a predecessor.
876 if (k == VREL_NONE || !single_pred_p (e->dest))
877 return;
878
879 if (dump_file && (dump_flags & TDF_DETAILS))
880 {
881 value_relation vr (k, op1, op2);
882 fprintf (dump_file, " Registering value_relation ");
883 vr.dump (dump_file);
884 fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index);
885 }
886
887 register_relation (e->dest, k, op1, op2);
888 }
889
890 // Register relation K between OP! and OP2 in block BB.
891 // This creates the record and searches for existing records in the dominator
892 // tree to merge with.
893
894 void
register_relation(basic_block bb,relation_kind k,tree op1,tree op2)895 dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
896 tree op2)
897 {
898 // If the 2 ssa_names are the same, do nothing. An equivalence is implied,
899 // and no other relation makes sense.
900 if (op1 == op2)
901 return;
902
903 // Equivalencies are handled by the equivalence oracle.
904 if (k == EQ_EXPR)
905 equiv_oracle::register_relation (bb, k, op1, op2);
906 else
907 {
908 relation_chain *ptr = set_one_relation (bb, k, op1, op2);
909 if (ptr)
910 register_transitives (bb, *ptr);
911 }
912 }
913
914 // Register relation K between OP! and OP2 in block BB.
915 // This creates the record and searches for existing records in the dominator
916 // tree to merge with. Return the record, or NULL if no record was created.
917
918 relation_chain *
set_one_relation(basic_block bb,relation_kind k,tree op1,tree op2)919 dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1,
920 tree op2)
921 {
922 gcc_checking_assert (k != VREL_NONE && k != EQ_EXPR);
923
924 value_relation vr(k, op1, op2);
925 int bbi = bb->index;
926
927 if (bbi >= (int)m_relations.length())
928 m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
929
930 // Summary bitmap indicating what ssa_names have relations in this BB.
931 bitmap bm = m_relations[bbi].m_names;
932 if (!bm)
933 bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps);
934 unsigned v1 = SSA_NAME_VERSION (op1);
935 unsigned v2 = SSA_NAME_VERSION (op2);
936
937 relation_kind curr;
938 relation_chain *ptr;
939 curr = find_relation_block (bbi, v1, v2, &ptr);
940 // There is an existing relation in this block, just intersect with it.
941 if (curr != VREL_NONE)
942 {
943 if (dump_file && (dump_flags & TDF_DETAILS))
944 {
945 fprintf (dump_file, " Intersecting with existing ");
946 ptr->dump (dump_file);
947 }
948 // Check into whether we can simply replace the relation rather than
949 // intersecting it. THis may help with some optimistic iterative
950 // updating algorithms.
951 ptr->intersect (vr);
952 if (dump_file && (dump_flags & TDF_DETAILS))
953 {
954 fprintf (dump_file, " to produce ");
955 ptr->dump (dump_file);
956 fprintf (dump_file, "\n");
957 }
958 }
959 else
960 {
961 if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
962 {
963 if (dump_file && (dump_flags & TDF_DETAILS))
964 fprintf (dump_file, " Not registered due to bb being full\n");
965 return NULL;
966 }
967 m_relations[bbi].m_num_relations++;
968 // Check for an existing relation further up the DOM chain.
969 // By including dominating relations, The first one found in any search
970 // will be the aggregate of all the previous ones.
971 curr = find_relation_dom (bb, v1, v2);
972 if (curr != VREL_NONE)
973 k = relation_intersect (curr, k);
974
975 bitmap_set_bit (bm, v1);
976 bitmap_set_bit (bm, v2);
977 bitmap_set_bit (m_relation_set, v1);
978 bitmap_set_bit (m_relation_set, v2);
979
980 ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
981 sizeof (relation_chain));
982 ptr->set_relation (k, op1, op2);
983 ptr->m_next = m_relations[bbi].m_head;
984 m_relations[bbi].m_head = ptr;
985 }
986 return ptr;
987 }
988
989 // Starting at ROOT_BB search the DOM tree looking for relations which
990 // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are
991 // bitmaps for op1/op2 and any of their equivalences that should also be
992 // considered.
993
994 void
register_transitives(basic_block root_bb,const value_relation & relation)995 dom_oracle::register_transitives (basic_block root_bb,
996 const value_relation &relation)
997 {
998 basic_block bb;
999 // Only apply transitives to certain kinds of operations.
1000 switch (relation.kind ())
1001 {
1002 case LE_EXPR:
1003 case LT_EXPR:
1004 case GT_EXPR:
1005 case GE_EXPR:
1006 break;
1007 default:
1008 return;
1009 }
1010
1011 const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb);
1012 const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb);
1013
1014 for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1015 {
1016 int bbi = bb->index;
1017 if (bbi >= (int)m_relations.length())
1018 continue;
1019 const_bitmap bm = m_relations[bbi].m_names;
1020 if (!bm)
1021 continue;
1022 if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2))
1023 continue;
1024 // At least one of the 2 ops has a relation in this block.
1025 relation_chain *ptr;
1026 for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next)
1027 {
1028 // In the presence of an equivalence, 2 operands may do not
1029 // naturally match. ie with equivalence a_2 == b_3
1030 // given c_1 < a_2 && b_3 < d_4
1031 // convert the second relation (b_3 < d_4) to match any
1032 // equivalences to found in the first relation.
1033 // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the
1034 // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4
1035
1036 tree r1, r2;
1037 tree p1 = ptr->op1 ();
1038 tree p2 = ptr->op2 ();
1039 // Find which equivalence is in the first operand.
1040 if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1)))
1041 r1 = p1;
1042 else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2)))
1043 r1 = p2;
1044 else
1045 r1 = NULL_TREE;
1046
1047 // Find which equivalence is in the second operand.
1048 if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1)))
1049 r2 = p1;
1050 else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2)))
1051 r2 = p2;
1052 else
1053 r2 = NULL_TREE;
1054
1055 // Ignore if both NULL (not relevant relation) or the same,
1056 if (r1 == r2)
1057 continue;
1058
1059 // Any operand not an equivalence, just take the real operand.
1060 if (!r1)
1061 r1 = relation.op1 ();
1062 if (!r2)
1063 r2 = relation.op2 ();
1064
1065 value_relation nr (relation.kind (), r1, r2);
1066 if (nr.apply_transitive (*ptr))
1067 {
1068 if (!set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ()))
1069 return;
1070 if (dump_file && (dump_flags & TDF_DETAILS))
1071 {
1072 fprintf (dump_file, " Registering transitive relation ");
1073 nr.dump (dump_file);
1074 fputc ('\n', dump_file);
1075 }
1076 }
1077
1078 }
1079 }
1080 }
1081
1082 // Find the relation between any ssa_name in B1 and any name in B2 in block BB.
1083 // This will allow equivalencies to be applied to any SSA_NAME in a relation.
1084
1085 relation_kind
find_relation_block(unsigned bb,const_bitmap b1,const_bitmap b2) const1086 dom_oracle::find_relation_block (unsigned bb, const_bitmap b1,
1087 const_bitmap b2) const
1088 {
1089 if (bb >= m_relations.length())
1090 return VREL_NONE;
1091
1092 return m_relations[bb].find_relation (b1, b2);
1093 }
1094
1095 // Search the DOM tree for a relation between an element of equivalency set B1
1096 // and B2, starting with block BB.
1097
1098 relation_kind
query_relation(basic_block bb,const_bitmap b1,const_bitmap b2)1099 dom_oracle::query_relation (basic_block bb, const_bitmap b1,
1100 const_bitmap b2)
1101 {
1102 relation_kind r;
1103 if (bitmap_equal_p (b1, b2))
1104 return EQ_EXPR;
1105
1106 // If either name does not occur in a relation anywhere, there isnt one.
1107 if (!bitmap_intersect_p (m_relation_set, b1)
1108 || !bitmap_intersect_p (m_relation_set, b2))
1109 return VREL_NONE;
1110
1111 // Search each block in the DOM tree checking.
1112 for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1113 {
1114 r = find_relation_block (bb->index, b1, b2);
1115 if (r != VREL_NONE)
1116 return r;
1117 }
1118 return VREL_NONE;
1119
1120 }
1121
1122 // Find a relation in block BB between ssa version V1 and V2. If a relation
1123 // is found, return a pointer to the chain object in OBJ.
1124
1125 relation_kind
find_relation_block(int bb,unsigned v1,unsigned v2,relation_chain ** obj) const1126 dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2,
1127 relation_chain **obj) const
1128 {
1129 if (bb >= (int)m_relations.length())
1130 return VREL_NONE;
1131
1132 const_bitmap bm = m_relations[bb].m_names;
1133 if (!bm)
1134 return VREL_NONE;
1135
1136 // If both b1 and b2 aren't referenced in thie block, cant be a relation
1137 if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2))
1138 return VREL_NONE;
1139
1140 relation_chain *ptr;
1141 for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next)
1142 {
1143 unsigned op1 = SSA_NAME_VERSION (ptr->op1 ());
1144 unsigned op2 = SSA_NAME_VERSION (ptr->op2 ());
1145 if (v1 == op1 && v2 == op2)
1146 {
1147 if (obj)
1148 *obj = ptr;
1149 return ptr->kind ();
1150 }
1151 if (v1 == op2 && v2 == op1)
1152 {
1153 if (obj)
1154 *obj = ptr;
1155 return relation_swap (ptr->kind ());
1156 }
1157 }
1158
1159 return VREL_NONE;
1160 }
1161
1162 // Find a relation between SSA version V1 and V2 in the dominator tree
1163 // starting with block BB
1164
1165 relation_kind
find_relation_dom(basic_block bb,unsigned v1,unsigned v2) const1166 dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const
1167 {
1168 relation_kind r;
1169 // IF either name does not occur in a relation anywhere, there isnt one.
1170 if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2))
1171 return VREL_NONE;
1172
1173 for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1174 {
1175 r = find_relation_block (bb->index, v1, v2);
1176 if (r != VREL_NONE)
1177 return r;
1178 }
1179 return VREL_NONE;
1180
1181 }
1182
1183 // Query if there is a relation between SSA1 and SS2 in block BB or a
1184 // dominator of BB
1185
1186 relation_kind
query_relation(basic_block bb,tree ssa1,tree ssa2)1187 dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1188 {
1189 relation_kind kind;
1190 unsigned v1 = SSA_NAME_VERSION (ssa1);
1191 unsigned v2 = SSA_NAME_VERSION (ssa2);
1192 if (v1 == v2)
1193 return EQ_EXPR;
1194
1195 // Check for equivalence first. They must be in each equivalency set.
1196 const_bitmap equiv1 = equiv_set (ssa1, bb);
1197 const_bitmap equiv2 = equiv_set (ssa2, bb);
1198 if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1))
1199 return EQ_EXPR;
1200
1201 // Initially look for a direct relationship and just return that.
1202 kind = find_relation_dom (bb, v1, v2);
1203 if (kind != VREL_NONE)
1204 return kind;
1205
1206 // Query using the equiovalence sets.
1207 kind = query_relation (bb, equiv1, equiv2);
1208 return kind;
1209 }
1210
1211 // Dump all the relations in block BB to file F.
1212
1213 void
dump(FILE * f,basic_block bb) const1214 dom_oracle::dump (FILE *f, basic_block bb) const
1215 {
1216 equiv_oracle::dump (f,bb);
1217
1218 if (bb->index >= (int)m_relations.length ())
1219 return;
1220 if (!m_relations[bb->index].m_names)
1221 return;
1222
1223 relation_chain *ptr = m_relations[bb->index].m_head;
1224 for (; ptr; ptr = ptr->m_next)
1225 {
1226 fprintf (f, "Relational : ");
1227 ptr->dump (f);
1228 fprintf (f, "\n");
1229 }
1230 }
1231
1232 // Dump all the relations known to file F.
1233
1234 void
dump(FILE * f) const1235 dom_oracle::dump (FILE *f) const
1236 {
1237 fprintf (f, "Relation dump\n");
1238 for (unsigned i = 0; i < m_relations.length (); i++)
1239 if (BASIC_BLOCK_FOR_FN (cfun, i))
1240 {
1241 fprintf (f, "BB%d\n", i);
1242 dump (f, BASIC_BLOCK_FOR_FN (cfun, i));
1243 }
1244 }
1245
1246 void
debug() const1247 relation_oracle::debug () const
1248 {
1249 dump (stderr);
1250 }
1251
path_oracle(relation_oracle * oracle)1252 path_oracle::path_oracle (relation_oracle *oracle)
1253 {
1254 set_root_oracle (oracle);
1255 bitmap_obstack_initialize (&m_bitmaps);
1256 obstack_init (&m_chain_obstack);
1257
1258 // Initialize header records.
1259 m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps);
1260 m_equiv.m_bb = NULL;
1261 m_equiv.m_next = NULL;
1262 m_relations.m_names = BITMAP_ALLOC (&m_bitmaps);
1263 m_relations.m_head = NULL;
1264 m_killed_defs = BITMAP_ALLOC (&m_bitmaps);
1265 }
1266
~path_oracle()1267 path_oracle::~path_oracle ()
1268 {
1269 obstack_free (&m_chain_obstack, NULL);
1270 bitmap_obstack_release (&m_bitmaps);
1271 }
1272
1273 // Return the equiv set for SSA, and if there isn't one, check for equivs
1274 // starting in block BB.
1275
1276 const_bitmap
equiv_set(tree ssa,basic_block bb)1277 path_oracle::equiv_set (tree ssa, basic_block bb)
1278 {
1279 // Check the list first.
1280 equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa));
1281 if (ptr)
1282 return ptr->m_names;
1283
1284 // Otherwise defer to the root oracle.
1285 if (m_root)
1286 return m_root->equiv_set (ssa, bb);
1287
1288 // Allocate a throw away bitmap if there isn't a root oracle.
1289 bitmap tmp = BITMAP_ALLOC (&m_bitmaps);
1290 bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa));
1291 return tmp;
1292 }
1293
1294 // Register an equivalence between SSA1 and SSA2 resolving unkowns from
1295 // block BB.
1296
1297 void
register_equiv(basic_block bb,tree ssa1,tree ssa2)1298 path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2)
1299 {
1300 const_bitmap equiv_1 = equiv_set (ssa1, bb);
1301 const_bitmap equiv_2 = equiv_set (ssa2, bb);
1302
1303 // Check if they are the same set, if so, we're done.
1304 if (bitmap_equal_p (equiv_1, equiv_2))
1305 return;
1306
1307 // Don't mess around, simply create a new record and insert it first.
1308 bitmap b = BITMAP_ALLOC (&m_bitmaps);
1309 valid_equivs (b, equiv_1, bb);
1310 valid_equivs (b, equiv_2, bb);
1311
1312 equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1313 sizeof (equiv_chain));
1314 ptr->m_names = b;
1315 ptr->m_bb = NULL;
1316 ptr->m_next = m_equiv.m_next;
1317 m_equiv.m_next = ptr;
1318 bitmap_ior_into (m_equiv.m_names, b);
1319 }
1320
1321 // Register killing definition of an SSA_NAME.
1322
1323 void
killing_def(tree ssa)1324 path_oracle::killing_def (tree ssa)
1325 {
1326 if (dump_file && (dump_flags & TDF_DETAILS))
1327 {
1328 fprintf (dump_file, " Registering killing_def (path_oracle) ");
1329 print_generic_expr (dump_file, ssa, TDF_SLIM);
1330 fprintf (dump_file, "\n");
1331 }
1332
1333 unsigned v = SSA_NAME_VERSION (ssa);
1334
1335 bitmap_set_bit (m_killed_defs, v);
1336
1337 // Walk the equivalency list and remove SSA from any equivalencies.
1338 if (bitmap_bit_p (m_equiv.m_names, v))
1339 {
1340 for (equiv_chain *ptr = m_equiv.m_next; ptr; ptr = ptr->m_next)
1341 if (bitmap_bit_p (ptr->m_names, v))
1342 bitmap_clear_bit (ptr->m_names, v);
1343 }
1344 else
1345 bitmap_set_bit (m_equiv.m_names, v);
1346
1347 // Now add an equivalency with itself so we don't look to the root oracle.
1348 bitmap b = BITMAP_ALLOC (&m_bitmaps);
1349 bitmap_set_bit (b, v);
1350 equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack,
1351 sizeof (equiv_chain));
1352 ptr->m_names = b;
1353 ptr->m_bb = NULL;
1354 ptr->m_next = m_equiv.m_next;
1355 m_equiv.m_next = ptr;
1356
1357 // Walk the relation list and remove SSA from any relations.
1358 if (!bitmap_bit_p (m_relations.m_names, v))
1359 return;
1360
1361 bitmap_clear_bit (m_relations.m_names, v);
1362 relation_chain **prev = &(m_relations.m_head);
1363 relation_chain *next = NULL;
1364 for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next)
1365 {
1366 gcc_checking_assert (*prev == ptr);
1367 next = ptr->m_next;
1368 if (SSA_NAME_VERSION (ptr->op1 ()) == v
1369 || SSA_NAME_VERSION (ptr->op2 ()) == v)
1370 *prev = ptr->m_next;
1371 else
1372 prev = &(ptr->m_next);
1373 }
1374 }
1375
1376 // Register relation K between SSA1 and SSA2, resolving unknowns by
1377 // querying from BB.
1378
1379 void
register_relation(basic_block bb,relation_kind k,tree ssa1,tree ssa2)1380 path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1,
1381 tree ssa2)
1382 {
1383 if (dump_file && (dump_flags & TDF_DETAILS))
1384 {
1385 value_relation vr (k, ssa1, ssa2);
1386 fprintf (dump_file, " Registering value_relation (path_oracle) ");
1387 vr.dump (dump_file);
1388 fprintf (dump_file, " (root: bb%d)\n", bb->index);
1389 }
1390
1391 relation_kind curr = query_relation (bb, ssa1, ssa2);
1392 if (curr != VREL_NONE)
1393 k = relation_intersect (curr, k);
1394
1395 if (k == EQ_EXPR)
1396 {
1397 register_equiv (bb, ssa1, ssa2);
1398 return;
1399 }
1400
1401 bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1));
1402 bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2));
1403 relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
1404 sizeof (relation_chain));
1405 ptr->set_relation (k, ssa1, ssa2);
1406 ptr->m_next = m_relations.m_head;
1407 m_relations.m_head = ptr;
1408 }
1409
1410 // Query for a relationship between equiv set B1 and B2, resolving unknowns
1411 // starting at block BB.
1412
1413 relation_kind
query_relation(basic_block bb,const_bitmap b1,const_bitmap b2)1414 path_oracle::query_relation (basic_block bb, const_bitmap b1, const_bitmap b2)
1415 {
1416 if (bitmap_equal_p (b1, b2))
1417 return EQ_EXPR;
1418
1419 relation_kind k = m_relations.find_relation (b1, b2);
1420
1421 // Do not look at the root oracle for names that have been killed
1422 // along the path.
1423 if (bitmap_intersect_p (m_killed_defs, b1)
1424 || bitmap_intersect_p (m_killed_defs, b2))
1425 return k;
1426
1427 if (k == VREL_NONE && m_root)
1428 k = m_root->query_relation (bb, b1, b2);
1429
1430 return k;
1431 }
1432
1433 // Query for a relationship between SSA1 and SSA2, resolving unknowns
1434 // starting at block BB.
1435
1436 relation_kind
query_relation(basic_block bb,tree ssa1,tree ssa2)1437 path_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2)
1438 {
1439 unsigned v1 = SSA_NAME_VERSION (ssa1);
1440 unsigned v2 = SSA_NAME_VERSION (ssa2);
1441
1442 if (v1 == v2)
1443 return EQ_EXPR;
1444
1445 const_bitmap equiv_1 = equiv_set (ssa1, bb);
1446 const_bitmap equiv_2 = equiv_set (ssa2, bb);
1447 if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1))
1448 return EQ_EXPR;
1449
1450 return query_relation (bb, equiv_1, equiv_2);
1451 }
1452
1453 // Reset any relations registered on this path.
1454
1455 void
reset_path()1456 path_oracle::reset_path ()
1457 {
1458 m_equiv.m_next = NULL;
1459 bitmap_clear (m_equiv.m_names);
1460 m_relations.m_head = NULL;
1461 bitmap_clear (m_relations.m_names);
1462 }
1463
1464 // Dump relation in basic block... Do nothing here.
1465
1466 void
dump(FILE *,basic_block) const1467 path_oracle::dump (FILE *, basic_block) const
1468 {
1469 }
1470
1471 // Dump the relations and equivalencies found in the path.
1472
1473 void
dump(FILE * f) const1474 path_oracle::dump (FILE *f) const
1475 {
1476 equiv_chain *ptr = m_equiv.m_next;
1477 relation_chain *ptr2 = m_relations.m_head;
1478
1479 if (ptr || ptr2)
1480 fprintf (f, "\npath_oracle:\n");
1481
1482 for (; ptr; ptr = ptr->m_next)
1483 ptr->dump (f);
1484
1485 for (; ptr2; ptr2 = ptr2->m_next)
1486 {
1487 fprintf (f, "Relational : ");
1488 ptr2->dump (f);
1489 fprintf (f, "\n");
1490 }
1491 }
1492