]>
Commit | Line | Data |
---|---|---|
3aaa69e5 AM |
1 | /* Header file for the value range relational processing. |
2 | Copyright (C) 2020-2021 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 | |
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 | |
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 | |
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 | ||
675a3e40 | 115 | // Intersect relation R1 with relation R2 and return the resulting relation. |
3aaa69e5 AM |
116 | |
117 | relation_kind | |
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 | |
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 | ||
675a3e40 AM |
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 | |
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 | ||
3aaa69e5 AM |
191 | // ------------------------------------------------------------------------- |
192 | ||
193 | // This class represents an equivalency set, and contains a link to the next | |
194 | // one in the list to be searched. | |
195 | ||
196 | // The very first element in the m_equiv chain is actually just a summary | |
197 | // element in which the m_names bitmap is used to indicate that an ssa_name | |
198 | // has an equivalence set in this block. | |
199 | // This allows for much faster traversal of the DOM chain, as a search for | |
200 | // SSA_NAME simply requires walking the DOM chain until a block is found | |
201 | // which has the bit for SSA_NAME set. Then scan for the equivalency set in | |
202 | // that block. No previous blcoks need be searched. | |
203 | ||
204 | class equiv_chain | |
205 | { | |
206 | public: | |
207 | bitmap m_names; // ssa-names in equiv set. | |
208 | basic_block m_bb; // Block this belongs to | |
209 | equiv_chain *m_next; // Next in block list. | |
210 | void dump (FILE *f) const; // Show names in this list. | |
211 | }; | |
212 | ||
213 | ||
214 | // Dump the names in this equivalence set. | |
215 | ||
216 | void | |
217 | equiv_chain::dump (FILE *f) const | |
218 | { | |
219 | bitmap_iterator bi; | |
220 | unsigned i; | |
221 | ||
222 | if (!m_names) | |
223 | return; | |
224 | fprintf (f, "Equivalence set : ["); | |
225 | unsigned c = 0; | |
226 | EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi) | |
227 | { | |
228 | if (ssa_name (i)) | |
229 | { | |
230 | if (c++) | |
231 | fprintf (f, ", "); | |
232 | print_generic_expr (f, ssa_name (i), TDF_SLIM); | |
233 | } | |
234 | } | |
235 | fprintf (f, "]\n"); | |
236 | } | |
237 | ||
238 | // Instantiate an equivalency oracle. | |
239 | ||
240 | equiv_oracle::equiv_oracle () | |
241 | { | |
242 | bitmap_obstack_initialize (&m_bitmaps); | |
243 | m_equiv.create (0); | |
244 | m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
245 | m_equiv_set = BITMAP_ALLOC (&m_bitmaps); | |
246 | obstack_init (&m_chain_obstack); | |
247 | } | |
248 | ||
249 | // Destruct an equivalency oracle. | |
250 | ||
251 | equiv_oracle::~equiv_oracle () | |
252 | { | |
253 | obstack_free (&m_chain_obstack, NULL); | |
254 | m_equiv.release (); | |
255 | bitmap_obstack_release (&m_bitmaps); | |
256 | } | |
257 | ||
258 | // Find and return the equivalency set for SSA along the dominators of BB. | |
259 | // This is the external API. | |
260 | ||
261 | const_bitmap | |
262 | equiv_oracle::equiv_set (tree ssa, basic_block bb) const | |
263 | { | |
264 | // Search the dominator tree for an equivalency. | |
265 | equiv_chain *equiv = find_equiv_dom (ssa, bb); | |
266 | if (equiv) | |
267 | return equiv->m_names; | |
268 | ||
269 | return NULL; | |
270 | } | |
271 | ||
272 | ||
273 | // If SSA has an equivalence in block BB, find and return it. | |
274 | // Otherwise return NULL. | |
275 | ||
276 | equiv_chain * | |
277 | equiv_oracle::find_equiv_block (unsigned ssa, int bb) const | |
278 | { | |
279 | equiv_chain *ptr = NULL; | |
280 | if (bb >= (int)m_equiv.length ()) | |
281 | return NULL; | |
282 | ||
283 | // If there are equiv sets and SSA is in one in this block, find it. | |
284 | // Otherwise return NULL. | |
285 | if (m_equiv[bb] && bitmap_bit_p (m_equiv[bb]->m_names, ssa)) | |
286 | { | |
287 | for (ptr = m_equiv[bb]->m_next; ptr; ptr = ptr->m_next) | |
288 | if (bitmap_bit_p (ptr->m_names, ssa)) | |
289 | break; | |
290 | } | |
291 | return ptr; | |
292 | } | |
293 | ||
294 | // Starting at block BB, walk the dominator chain looking for the nearest | |
295 | // equivalence set containing NAME. | |
296 | ||
297 | equiv_chain * | |
298 | equiv_oracle::find_equiv_dom (tree name, basic_block bb) const | |
299 | { | |
300 | unsigned v = SSA_NAME_VERSION (name); | |
301 | // Short circuit looking for names which have no equivalences. | |
302 | // Saves time looking for something which does not exist. | |
303 | if (!bitmap_bit_p (m_equiv_set, v)) | |
304 | return NULL; | |
305 | ||
306 | // NAME has at least once equivalence set, check to see if it has one along | |
307 | // the dominator tree. | |
308 | for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
309 | { | |
310 | equiv_chain *ptr = find_equiv_block (v, bb->index); | |
311 | if (ptr) | |
312 | return ptr; | |
313 | } | |
314 | return NULL; | |
315 | } | |
316 | ||
317 | // Register equivalance between ssa_name V and set EQUIV in block BB, | |
318 | ||
319 | bitmap | |
320 | equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv) | |
321 | { | |
322 | // V will have an equivalency now. | |
323 | bitmap_set_bit (m_equiv_set, v); | |
324 | ||
325 | // If that equiv chain is in this block, simply use it. | |
326 | if (equiv->m_bb == bb) | |
327 | { | |
328 | bitmap_set_bit (equiv->m_names, v); | |
329 | bitmap_set_bit (m_equiv[bb->index]->m_names, v); | |
330 | return NULL; | |
331 | } | |
332 | ||
333 | // Otherwise create an equivalence for this block which is a copy | |
334 | // of equiv, the add V to the set. | |
335 | bitmap b = BITMAP_ALLOC (&m_bitmaps); | |
336 | bitmap_copy (b, equiv->m_names); | |
337 | bitmap_set_bit (b, v); | |
338 | return b; | |
339 | } | |
340 | ||
341 | // Register equivalence between set equiv_1 and equiv_2 in block BB. | |
342 | // Return NULL if either name can be merged with the other. Otherwise | |
343 | // return a pointer to the combined bitmap of names. This allows the | |
344 | // caller to do any setup required for a new element. | |
345 | ||
346 | bitmap | |
347 | equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1, | |
348 | equiv_chain *equiv_2) | |
349 | { | |
350 | // If equiv_1 is alreayd in BB, use it as the combined set. | |
351 | if (equiv_1->m_bb == bb) | |
352 | { | |
353 | bitmap_ior_into (equiv_1->m_names, equiv_2->m_names); | |
354 | // Its hard to delete from a single linked list, so | |
355 | // just clear the second one. | |
356 | if (equiv_2->m_bb == bb) | |
357 | bitmap_clear (equiv_2->m_names); | |
358 | else | |
359 | // Ensure equiv_2s names are in the summary for BB. | |
360 | bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names); | |
361 | return NULL; | |
362 | } | |
363 | // If equiv_2 is in BB, use it for the combined set. | |
364 | if (equiv_2->m_bb == bb) | |
365 | { | |
366 | bitmap_ior_into (equiv_2->m_names, equiv_1->m_names); | |
367 | // Add equiv_1 names into the summary. | |
368 | bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names); | |
369 | return NULL; | |
370 | } | |
371 | ||
372 | // At this point, neither equivalence is from this block. | |
373 | bitmap b = BITMAP_ALLOC (&m_bitmaps); | |
374 | bitmap_copy (b, equiv_1->m_names); | |
375 | bitmap_ior_into (b, equiv_2->m_names); | |
376 | return b; | |
377 | } | |
378 | ||
379 | ||
380 | // Register an equivalence between SSA1 and SSA2 in block BB. | |
381 | // The equivalence oracle maintains a vector of equivalencies indexed by basic | |
382 | // block. When an equivalence bteween SSA1 and SSA2 is registered in block BB, | |
383 | // a query is made as to what equivalences both names have already, and | |
384 | // any preexisting equivalences are merged to create a single equivalence | |
385 | // containing all the ssa_names in this basic block. | |
386 | ||
387 | void | |
388 | equiv_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2) | |
389 | { | |
390 | unsigned v1 = SSA_NAME_VERSION (ssa1); | |
391 | unsigned v2 = SSA_NAME_VERSION (ssa2); | |
392 | equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb); | |
393 | equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb); | |
394 | ||
395 | // Check if they are the same set | |
396 | if (equiv_1 && equiv_1 == equiv_2) | |
397 | return; | |
398 | ||
399 | bitmap equiv_set; | |
400 | ||
401 | // Case where we have 2 SSA_NAMEs that are not in any set. | |
402 | if (!equiv_1 && !equiv_2) | |
403 | { | |
404 | bitmap_set_bit (m_equiv_set, v1); | |
405 | bitmap_set_bit (m_equiv_set, v2); | |
406 | ||
407 | equiv_set = BITMAP_ALLOC (&m_bitmaps); | |
408 | bitmap_set_bit (equiv_set, v1); | |
409 | bitmap_set_bit (equiv_set, v2); | |
410 | } | |
411 | else if (!equiv_1 && equiv_2) | |
412 | equiv_set = register_equiv (bb, v1, equiv_2); | |
413 | else if (equiv_1 && !equiv_2) | |
414 | equiv_set = register_equiv (bb, v2, equiv_1); | |
415 | else | |
416 | equiv_set = register_equiv (bb, equiv_1, equiv_2); | |
417 | ||
418 | // A non-null return is a bitmap that is to be added to the current | |
419 | // block as a new equivalence. | |
420 | if (!equiv_set) | |
421 | return; | |
422 | ||
423 | equiv_chain *ptr; | |
424 | ||
425 | // Check if this is the first time a block has an equivalence added. | |
426 | // and create a header block. And set the summary for this block. | |
427 | if (!m_equiv[bb->index]) | |
428 | { | |
429 | ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, | |
430 | sizeof (equiv_chain)); | |
431 | ptr->m_names = BITMAP_ALLOC (&m_bitmaps); | |
432 | bitmap_copy (ptr->m_names, equiv_set); | |
433 | ptr->m_bb = bb; | |
434 | ptr->m_next = NULL; | |
435 | m_equiv[bb->index] = ptr; | |
436 | } | |
437 | ||
438 | // Now create the element for this equiv set and initialize it. | |
439 | ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain)); | |
440 | ptr->m_names = equiv_set; | |
441 | ptr->m_bb = bb; | |
442 | gcc_checking_assert (bb->index < (int)m_equiv.length ()); | |
443 | ptr->m_next = m_equiv[bb->index]->m_next; | |
444 | m_equiv[bb->index]->m_next = ptr; | |
445 | bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set); | |
446 | } | |
447 | ||
448 | // Make sure the BB vector is big enough and grow it if needed. | |
449 | ||
450 | void | |
451 | equiv_oracle::limit_check (basic_block bb) | |
452 | { | |
453 | int i = (bb) ? bb->index : last_basic_block_for_fn (cfun); | |
454 | if (i >= (int)m_equiv.length ()) | |
455 | m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
456 | } | |
457 | ||
458 | // Dump the equivalence sets in BB to file F. | |
459 | ||
460 | void | |
461 | equiv_oracle::dump (FILE *f, basic_block bb) const | |
462 | { | |
463 | if (bb->index >= (int)m_equiv.length ()) | |
464 | return; | |
465 | if (!m_equiv[bb->index]) | |
466 | return; | |
467 | ||
468 | equiv_chain *ptr = m_equiv[bb->index]->m_next; | |
469 | for (; ptr; ptr = ptr->m_next) | |
470 | ptr->dump (f); | |
471 | } | |
472 | ||
473 | // Dump all equivalence sets known to the oracle. | |
474 | ||
475 | void | |
476 | equiv_oracle::dump (FILE *f) const | |
477 | { | |
478 | fprintf (f, "Equivalency dump\n"); | |
479 | for (unsigned i = 0; i < m_equiv.length (); i++) | |
ce0b409f | 480 | if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i)) |
3aaa69e5 AM |
481 | { |
482 | fprintf (f, "BB%d\n", i); | |
483 | dump (f, BASIC_BLOCK_FOR_FN (cfun, i)); | |
484 | } | |
485 | } | |
486 | ||
487 | ||
488 | // -------------------------------------------------------------------------- | |
489 | ||
490 | // The value-relation class is used to encapsulate the represention of an | |
491 | // individual relation between 2 ssa-names, and to facilitate operating on | |
492 | // the relation. | |
493 | ||
494 | class value_relation | |
495 | { | |
496 | public: | |
497 | value_relation (); | |
498 | value_relation (relation_kind kind, tree n1, tree n2); | |
499 | void set_relation (relation_kind kind, tree n1, tree n2); | |
500 | ||
501 | inline relation_kind kind () const { return related; } | |
502 | inline tree op1 () const { return name1; } | |
503 | inline tree op2 () const { return name2; } | |
504 | ||
505 | bool union_ (value_relation &p); | |
506 | bool intersect (value_relation &p); | |
507 | void negate (); | |
675a3e40 | 508 | bool apply_transitive (const value_relation &rel); |
3aaa69e5 AM |
509 | |
510 | void dump (FILE *f) const; | |
511 | private: | |
512 | relation_kind related; | |
513 | tree name1, name2; | |
514 | }; | |
515 | ||
516 | // Set relation R between ssa_name N1 and N2. | |
517 | ||
518 | inline void | |
519 | value_relation::set_relation (relation_kind r, tree n1, tree n2) | |
520 | { | |
521 | gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2)); | |
522 | related = r; | |
523 | name1 = n1; | |
524 | name2 = n2; | |
525 | } | |
526 | ||
527 | // Default constructor. | |
528 | ||
529 | inline | |
530 | value_relation::value_relation () | |
531 | { | |
532 | related = VREL_NONE; | |
533 | name1 = NULL_TREE; | |
534 | name2 = NULL_TREE; | |
535 | } | |
536 | ||
537 | // Constructor for relation R between SSA version N1 nd N2. | |
538 | ||
539 | inline | |
540 | value_relation::value_relation (relation_kind kind, tree n1, tree n2) | |
541 | { | |
542 | set_relation (kind, n1, n2); | |
543 | } | |
544 | ||
545 | // Negate the current relation. | |
546 | ||
547 | void | |
548 | value_relation::negate () | |
549 | { | |
550 | related = relation_negate (related); | |
551 | } | |
552 | ||
3aaa69e5 AM |
553 | // Perform an intersection between 2 relations. *this &&= p. |
554 | ||
555 | bool | |
556 | value_relation::intersect (value_relation &p) | |
557 | { | |
558 | // Save previous value | |
559 | relation_kind old = related; | |
560 | ||
561 | if (p.op1 () == op1 () && p.op2 () == op2 ()) | |
562 | related = relation_intersect (kind (), p.kind ()); | |
563 | else if (p.op2 () == op1 () && p.op1 () == op2 ()) | |
564 | related = relation_intersect (kind (), relation_swap (p.kind ())); | |
565 | else | |
566 | return false; | |
567 | ||
568 | return old != related; | |
569 | } | |
570 | ||
571 | // Perform a union between 2 relations. *this ||= p. | |
572 | ||
573 | bool | |
574 | value_relation::union_ (value_relation &p) | |
575 | { | |
576 | // Save previous value | |
577 | relation_kind old = related; | |
578 | ||
579 | if (p.op1 () == op1 () && p.op2 () == op2 ()) | |
580 | related = relation_union (kind(), p.kind()); | |
581 | else if (p.op2 () == op1 () && p.op1 () == op2 ()) | |
582 | related = relation_union (kind(), relation_swap (p.kind ())); | |
583 | else | |
584 | return false; | |
585 | ||
586 | return old != related; | |
587 | } | |
588 | ||
675a3e40 AM |
589 | // Identify and apply any transitive relations between REL |
590 | // and THIS. Return true if there was a transformation. | |
591 | ||
592 | bool | |
593 | value_relation::apply_transitive (const value_relation &rel) | |
594 | { | |
595 | relation_kind k = VREL_NONE; | |
596 | ||
597 | // Idenity any common operand, and notrmalize the relations to | |
598 | // the form : A < B B < C produces A < C | |
599 | if (rel.op1 () == name2) | |
600 | { | |
601 | // A < B B < C | |
602 | if (rel.op2 () == name1) | |
603 | return false; | |
604 | k = relation_transitive (kind (), rel.kind ()); | |
605 | if (k != VREL_NONE) | |
606 | { | |
607 | related = k; | |
608 | name2 = rel.op2 (); | |
609 | return true; | |
610 | } | |
611 | } | |
612 | else if (rel.op1 () == name1) | |
613 | { | |
614 | // B > A B < C | |
615 | if (rel.op2 () == name2) | |
616 | return false; | |
617 | k = relation_transitive (relation_swap (kind ()), rel.kind ()); | |
618 | if (k != VREL_NONE) | |
619 | { | |
620 | related = k; | |
621 | name1 = name2; | |
622 | name2 = rel.op2 (); | |
623 | return true; | |
624 | } | |
625 | } | |
626 | else if (rel.op2 () == name2) | |
627 | { | |
628 | // A < B C > B | |
629 | if (rel.op1 () == name1) | |
630 | return false; | |
631 | k = relation_transitive (kind (), relation_swap (rel.kind ())); | |
632 | if (k != VREL_NONE) | |
633 | { | |
634 | related = k; | |
635 | name2 = rel.op1 (); | |
636 | return true; | |
637 | } | |
638 | } | |
639 | else if (rel.op2 () == name1) | |
640 | { | |
641 | // B > A C > B | |
642 | if (rel.op1 () == name2) | |
643 | return false; | |
644 | k = relation_transitive (relation_swap (kind ()), | |
645 | relation_swap (rel.kind ())); | |
646 | if (k != VREL_NONE) | |
647 | { | |
648 | related = k; | |
649 | name1 = name2; | |
650 | name2 = rel.op1 (); | |
651 | return true; | |
652 | } | |
653 | } | |
654 | return false; | |
655 | } | |
3aaa69e5 AM |
656 | |
657 | // Dump the relation to file F. | |
658 | ||
659 | void | |
660 | value_relation::dump (FILE *f) const | |
661 | { | |
662 | if (!name1 || !name2) | |
663 | { | |
664 | fprintf (f, "uninitialized"); | |
665 | return; | |
666 | } | |
667 | fputc ('(', f); | |
668 | print_generic_expr (f, op1 (), TDF_SLIM); | |
669 | print_relation (f, kind ()); | |
670 | print_generic_expr (f, op2 (), TDF_SLIM); | |
671 | fputc(')', f); | |
672 | } | |
673 | ||
674 | // This container is used to link relations in a chain. | |
675 | ||
676 | class relation_chain : public value_relation | |
677 | { | |
678 | public: | |
679 | relation_chain *m_next; | |
680 | }; | |
681 | ||
682 | // ------------------------------------------------------------------------ | |
683 | ||
684 | // Instantiate a relation oracle. | |
685 | ||
686 | relation_oracle::relation_oracle () | |
687 | { | |
688 | m_relations.create (0); | |
689 | m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
690 | m_relation_set = BITMAP_ALLOC (&m_bitmaps); | |
691 | m_tmp = BITMAP_ALLOC (&m_bitmaps); | |
675a3e40 | 692 | m_tmp2 = BITMAP_ALLOC (&m_bitmaps); |
3aaa69e5 AM |
693 | } |
694 | ||
695 | // Destruct a relation oracle. | |
696 | ||
697 | relation_oracle::~relation_oracle () | |
698 | { | |
699 | m_relations.release (); | |
700 | } | |
701 | ||
702 | // Register relation K between ssa_name OP1 and OP2 on STMT. | |
703 | ||
704 | void | |
705 | relation_oracle::register_relation (gimple *stmt, relation_kind k, tree op1, | |
706 | tree op2) | |
707 | { | |
708 | gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); | |
709 | gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); | |
710 | gcc_checking_assert (stmt && gimple_bb (stmt)); | |
711 | ||
712 | // Don't register lack of a relation. | |
713 | if (k == VREL_NONE) | |
714 | return; | |
715 | ||
716 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
717 | { | |
718 | value_relation vr (k, op1, op2); | |
719 | fprintf (dump_file, " Registering value_relation "); | |
720 | vr.dump (dump_file); | |
721 | fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index); | |
722 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
723 | } | |
724 | ||
725 | // This relation applies to the entire block, use STMT's block. | |
726 | // Equivalencies are handled by the equivalence oracle. | |
727 | if (k == EQ_EXPR) | |
728 | register_equiv (gimple_bb (stmt), op1, op2); | |
729 | else | |
730 | register_relation (gimple_bb (stmt), k, op1, op2); | |
731 | } | |
732 | ||
733 | // Register relation K between ssa_name OP1 and OP2 on edge E. | |
734 | ||
735 | void | |
736 | relation_oracle::register_relation (edge e, relation_kind k, tree op1, | |
737 | tree op2) | |
738 | { | |
739 | gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); | |
740 | gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); | |
741 | ||
742 | // Do not register lack of relation, or blocks which have more than | |
743 | // edge E for a predecessor. | |
744 | if (k == VREL_NONE || !single_pred_p (e->dest)) | |
745 | return; | |
746 | ||
747 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
748 | { | |
749 | value_relation vr (k, op1, op2); | |
750 | fprintf (dump_file, " Registering value_relation "); | |
751 | vr.dump (dump_file); | |
752 | fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index); | |
753 | } | |
754 | ||
755 | // Equivalencies are handled by the equivalence oracle. | |
756 | if (k == EQ_EXPR) | |
757 | register_equiv (e->dest, op1, op2); | |
758 | else | |
759 | register_relation (e->dest, k, op1, op2); | |
760 | } | |
761 | ||
762 | // Register relation K between OP! and OP2 in block BB. | |
763 | // This creates the record and searches for existing records in the dominator | |
764 | // tree to merge with. | |
675a3e40 AM |
765 | // TRANSITIVE_P is true if this is being registered as a transitive operation, |
766 | // and should not try to register further transitives. | |
3aaa69e5 AM |
767 | |
768 | void | |
769 | relation_oracle::register_relation (basic_block bb, relation_kind k, tree op1, | |
675a3e40 | 770 | tree op2, bool transitive_p) |
3aaa69e5 AM |
771 | { |
772 | gcc_checking_assert (k != VREL_NONE); | |
773 | ||
774 | value_relation vr(k, op1, op2); | |
775 | int bbi = bb->index; | |
776 | ||
777 | if (bbi >= (int)m_relations.length()) | |
778 | m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
779 | ||
780 | // Summary bitmap indicating what ssa_names have relations in this BB. | |
781 | bitmap bm = m_relations[bbi].m_names; | |
782 | if (!bm) | |
783 | bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps); | |
784 | unsigned v1 = SSA_NAME_VERSION (op1); | |
785 | unsigned v2 = SSA_NAME_VERSION (op2); | |
786 | ||
787 | relation_kind curr; | |
788 | relation_chain *ptr; | |
789 | curr = find_relation_block (bbi, v1, v2, &ptr); | |
790 | // There is an existing relation in this block, just intersect with it. | |
791 | if (curr != VREL_NONE) | |
792 | { | |
793 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
794 | { | |
795 | fprintf (dump_file, " Intersecting with existing "); | |
796 | ptr->dump (dump_file); | |
797 | } | |
798 | // Check into whether we can simply replace the relation rather than | |
799 | // intersecting it. THis may help with some optimistic iterative | |
800 | // updating algorithms. | |
801 | ptr->intersect (vr); | |
802 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
803 | { | |
804 | fprintf (dump_file, " to produce "); | |
805 | ptr->dump (dump_file); | |
806 | fprintf (dump_file, "\n"); | |
807 | } | |
675a3e40 AM |
808 | } |
809 | else | |
810 | { | |
811 | // Check for an existing relation further up the DOM chain. | |
812 | // By including dominating relations, The first one found in any search | |
813 | // will be the aggregate of all the previous ones. | |
814 | curr = find_relation_dom (bb, v1, v2); | |
815 | if (curr != VREL_NONE) | |
816 | k = relation_intersect (curr, k); | |
817 | ||
818 | bitmap_set_bit (bm, v1); | |
819 | bitmap_set_bit (bm, v2); | |
820 | bitmap_set_bit (m_relation_set, v1); | |
821 | bitmap_set_bit (m_relation_set, v2); | |
822 | ||
823 | ptr = (relation_chain *) obstack_alloc (&m_chain_obstack, | |
824 | sizeof (relation_chain)); | |
825 | ptr->set_relation (k, op1, op2); | |
826 | ptr->m_next = m_relations[bbi].m_head; | |
827 | m_relations[bbi].m_head = ptr;; | |
3aaa69e5 AM |
828 | } |
829 | ||
675a3e40 AM |
830 | if (!transitive_p) |
831 | register_transitives (bb, *ptr); | |
832 | } | |
833 | ||
834 | // Starting at ROOT_BB search the DOM tree looking for relations which | |
835 | // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are | |
836 | // bitmaps for op1/op2 and any of their equivalences that should also be | |
837 | // considered. | |
838 | ||
839 | void | |
840 | relation_oracle::register_transitives (basic_block root_bb, | |
841 | const value_relation &relation, | |
842 | const_bitmap equiv1, | |
843 | const_bitmap equiv2) | |
844 | { | |
845 | basic_block bb; | |
846 | for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
847 | { | |
848 | int bbi = bb->index; | |
849 | if (bbi >= (int)m_relations.length()) | |
850 | continue; | |
851 | const_bitmap bm = m_relations[bbi].m_names; | |
852 | if (!bm) | |
853 | continue; | |
854 | if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2)) | |
855 | continue; | |
856 | // At least one of the 2 ops has a relation in this block. | |
857 | relation_chain *ptr; | |
858 | for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next) | |
859 | { | |
860 | // In the presence of an equivalence, 2 operands may do not | |
861 | // naturally match. ie with equivalence a_2 == b_3 | |
862 | // given c_1 < a_2 && b_3 < d_4 | |
863 | // convert the second relation (b_3 < d_4) to match any | |
864 | // equivalences to found in the first relation. | |
865 | // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the | |
866 | // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4 | |
867 | ||
868 | tree r1, r2; | |
869 | tree p1 = ptr->op1 (); | |
870 | tree p2 = ptr->op2 (); | |
871 | // Find which equivalence is in the first operand. | |
872 | if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1))) | |
873 | r1 = p1; | |
874 | else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2))) | |
875 | r1 = p2; | |
876 | else | |
877 | r1 = NULL_TREE; | |
878 | ||
879 | // Find which equivalence is in the second operand. | |
880 | if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1))) | |
881 | r2 = p1; | |
882 | else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2))) | |
883 | r2 = p2; | |
884 | else | |
885 | r2 = NULL_TREE; | |
886 | ||
887 | // Ignore if both NULL (not relevant relation) or the same, | |
888 | if (r1 == r2) | |
889 | continue; | |
890 | ||
891 | // Any operand not an equivalence, just take the real operand. | |
892 | if (!r1) | |
893 | r1 = relation.op1 (); | |
894 | if (!r2) | |
895 | r2 = relation.op2 (); | |
896 | ||
897 | value_relation nr (relation.kind (), r1, r2); | |
898 | if (nr.apply_transitive (*ptr)) | |
899 | { | |
900 | register_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 (), | |
901 | true); | |
902 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
903 | { | |
904 | fprintf (dump_file, " Registering transitive relation "); | |
905 | nr.dump (dump_file); | |
906 | fputc ('\n', dump_file); | |
907 | } | |
908 | } | |
909 | ||
910 | } | |
911 | } | |
912 | } | |
913 | ||
914 | // Find adn register any transitive relations implied by RELATION occuring | |
915 | // in block BB. | |
916 | ||
917 | void | |
918 | relation_oracle::register_transitives (basic_block bb, | |
919 | const value_relation &relation) | |
920 | { | |
921 | // Only apply transitives to certain kinds of operations. | |
922 | switch (relation.kind ()) | |
923 | { | |
924 | case LE_EXPR: | |
925 | case LT_EXPR: | |
926 | case GT_EXPR: | |
927 | case GE_EXPR: | |
928 | break; | |
929 | default: | |
930 | return; | |
931 | } | |
932 | ||
933 | // Set up the bitmaps for op1 and op2, and if there are no equivalencies, | |
934 | // set just op1 or op2 in their own bitmap. | |
935 | const_bitmap equiv1 = equiv_set (relation.op1 (), bb); | |
936 | const_bitmap equiv2 = equiv_set (relation.op2 (), bb); | |
937 | if (equiv1) | |
938 | { | |
939 | if (equiv2) | |
940 | register_transitives (bb, relation, equiv1, equiv2); | |
941 | else | |
942 | { | |
943 | bitmap_clear (m_tmp); | |
944 | bitmap_set_bit (m_tmp, SSA_NAME_VERSION (relation.op2 ())); | |
945 | register_transitives (bb, relation, equiv1, m_tmp); | |
946 | } | |
947 | } | |
948 | else if (equiv2) | |
949 | { | |
950 | bitmap_clear (m_tmp); | |
951 | bitmap_set_bit (m_tmp, SSA_NAME_VERSION (relation.op1 ())); | |
952 | register_transitives (bb, relation, m_tmp, equiv2); | |
953 | } | |
954 | else | |
955 | { | |
956 | bitmap_clear (m_tmp); | |
957 | bitmap_clear (m_tmp2); | |
958 | bitmap_set_bit (m_tmp, SSA_NAME_VERSION (relation.op1 ())); | |
959 | bitmap_set_bit (m_tmp2, SSA_NAME_VERSION (relation.op2 ())); | |
960 | register_transitives (bb, relation, m_tmp, m_tmp2); | |
961 | } | |
3aaa69e5 AM |
962 | } |
963 | ||
964 | // Find the relation between any ssa_name in B1 and any name in B2 in block BB. | |
965 | // This will allow equivalencies to be applied to any SSA_NAME in a relation. | |
966 | ||
967 | relation_kind | |
968 | relation_oracle::find_relation_block (unsigned bb, const_bitmap b1, | |
969 | const_bitmap b2) | |
970 | { | |
971 | const_bitmap bm; | |
972 | if (bb >= m_relations.length()) | |
973 | return VREL_NONE; | |
974 | ||
975 | bm = m_relations[bb].m_names; | |
976 | if (!bm) | |
977 | return VREL_NONE; | |
978 | ||
979 | // If both b1 and b2 aren't referenced in thie block, cant be a relation | |
980 | if (!bitmap_intersect_p (bm, b1) || !bitmap_intersect_p (bm, b2)) | |
981 | return VREL_NONE; | |
982 | ||
983 | // Search for the fiorst relation that contains BOTH an element from B1 | |
984 | // and B2, and return that relation. | |
985 | for (relation_chain *ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next) | |
986 | { | |
987 | unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); | |
988 | unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); | |
ce0b409f | 989 | if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2)) |
3aaa69e5 | 990 | return ptr->kind (); |
ce0b409f | 991 | if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1)) |
3aaa69e5 AM |
992 | return relation_swap (ptr->kind ()); |
993 | } | |
994 | ||
995 | return VREL_NONE; | |
996 | } | |
997 | ||
998 | // Search the DOM tree for a relation between an element of B1 and B2, starting | |
999 | // with block BB. | |
1000 | ||
1001 | relation_kind | |
1002 | relation_oracle::find_relation_dom (basic_block bb, const_bitmap b1, | |
1003 | const_bitmap b2) | |
1004 | { | |
1005 | relation_kind r; | |
1006 | // If either name does not occur in a relation anywhere, there isnt one. | |
1007 | if (!bitmap_intersect_p (m_relation_set, b1) | |
1008 | || !bitmap_intersect_p (m_relation_set, b2)) | |
1009 | return VREL_NONE; | |
1010 | ||
1011 | // Search each block in the DOM tree checking. | |
1012 | for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
1013 | { | |
1014 | r = find_relation_block (bb->index, b1, b2); | |
1015 | if (r != VREL_NONE) | |
1016 | return r; | |
1017 | } | |
1018 | return VREL_NONE; | |
1019 | ||
1020 | } | |
1021 | ||
1022 | // Find a relation in block BB between ssa version V1 and V2. If a relation | |
1023 | // is found, return a pointer to the chain object in OBJ. | |
1024 | ||
1025 | relation_kind | |
1026 | relation_oracle::find_relation_block (int bb, unsigned v1, unsigned v2, | |
1027 | relation_chain **obj) | |
1028 | { | |
1029 | if (bb >= (int)m_relations.length()) | |
1030 | return VREL_NONE; | |
1031 | ||
1032 | const_bitmap bm = m_relations[bb].m_names; | |
1033 | if (!bm) | |
1034 | return VREL_NONE; | |
1035 | ||
1036 | // If both b1 and b2 aren't referenced in thie block, cant be a relation | |
1037 | if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2)) | |
1038 | return VREL_NONE; | |
1039 | ||
1040 | relation_chain *ptr; | |
1041 | for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next) | |
1042 | { | |
1043 | unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); | |
1044 | unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); | |
1045 | if (v1 == op1 && v2 == op2) | |
1046 | { | |
1047 | if (obj) | |
1048 | *obj = ptr; | |
1049 | return ptr->kind (); | |
1050 | } | |
1051 | if (v1 == op2 && v2 == op1) | |
1052 | { | |
1053 | if (obj) | |
1054 | *obj = ptr; | |
1055 | return relation_swap (ptr->kind ()); | |
1056 | } | |
1057 | } | |
1058 | ||
1059 | return VREL_NONE; | |
1060 | } | |
1061 | ||
1062 | // Find a relation between SSA version V1 and V2 in the dominator tree | |
1063 | // starting with block BB | |
1064 | ||
1065 | relation_kind | |
1066 | relation_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) | |
1067 | { | |
1068 | relation_kind r; | |
1069 | // IF either name does not occur in a relation anywhere, there isnt one. | |
1070 | if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2)) | |
1071 | return VREL_NONE; | |
1072 | ||
1073 | for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
1074 | { | |
1075 | r = find_relation_block (bb->index, v1, v2); | |
1076 | if (r != VREL_NONE) | |
1077 | return r; | |
1078 | } | |
1079 | return VREL_NONE; | |
1080 | ||
1081 | } | |
1082 | ||
1083 | // Query if there is a relation between SSA1 and SS2 in block BB or a | |
1084 | // dominator of BB | |
1085 | ||
1086 | relation_kind | |
1087 | relation_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) | |
1088 | { | |
1089 | relation_kind kind; | |
1090 | unsigned v1 = SSA_NAME_VERSION (ssa1); | |
1091 | unsigned v2 = SSA_NAME_VERSION (ssa2); | |
1092 | if (v1 == v2) | |
1093 | return EQ_EXPR; | |
1094 | ||
1095 | // Check for equivalence first. | |
1096 | const_bitmap equiv1 = equiv_set (ssa1, bb); | |
1097 | if (equiv1 && bitmap_bit_p (equiv1, v2)) | |
1098 | return EQ_EXPR; | |
1099 | ||
1100 | // Initially look for a direct relationship and just return that. | |
1101 | kind = find_relation_dom (bb, v1, v2); | |
1102 | if (kind != VREL_NONE) | |
1103 | return kind; | |
1104 | ||
3aaa69e5 | 1105 | // If v2 isn't in v1s equiv set, then v1 shouldn't be in v2's set either. |
d3fa7747 AM |
1106 | // It is possible for out-of-order dominator processing to have an out of |
1107 | // sync set of equivalences.. Down the road, when we do full updates, | |
1108 | // change this to an assert to ensure everything is in sync. | |
3aaa69e5 | 1109 | const_bitmap equiv2 = equiv_set (ssa2, bb); |
d3fa7747 AM |
1110 | if (equiv2 && bitmap_bit_p (equiv2, v1)) |
1111 | return EQ_EXPR; | |
3aaa69e5 | 1112 | |
d3fa7747 | 1113 | // If not equal, see if there is a relationship between equivalences. |
3aaa69e5 AM |
1114 | if (!equiv1 && !equiv2) |
1115 | kind = VREL_NONE; | |
1116 | else if (!equiv1) | |
1117 | { | |
1118 | bitmap_clear (m_tmp); | |
1119 | bitmap_set_bit (m_tmp, v1); | |
1120 | kind = find_relation_dom (bb, m_tmp, equiv2); | |
1121 | } | |
1122 | else if (!equiv2) | |
1123 | { | |
1124 | bitmap_clear (m_tmp); | |
1125 | bitmap_set_bit (m_tmp, v2); | |
1126 | kind = find_relation_dom (bb, equiv1, m_tmp); | |
1127 | } | |
1128 | else | |
1129 | kind = find_relation_dom (bb, equiv1, equiv2); | |
1130 | return kind; | |
1131 | } | |
1132 | ||
1133 | // Dump all the relations in block BB to file F. | |
1134 | ||
1135 | void | |
1136 | relation_oracle::dump (FILE *f, basic_block bb) const | |
1137 | { | |
1138 | equiv_oracle::dump (f,bb); | |
1139 | ||
1140 | if (bb->index >= (int)m_relations.length ()) | |
1141 | return; | |
1142 | if (!m_relations[bb->index].m_names) | |
1143 | return; | |
1144 | ||
1145 | relation_chain *ptr = m_relations[bb->index].m_head; | |
1146 | for (; ptr; ptr = ptr->m_next) | |
1147 | { | |
1148 | fprintf (f, "Relational : "); | |
1149 | ptr->dump (f); | |
1150 | fprintf (f, "\n"); | |
1151 | } | |
1152 | } | |
1153 | ||
1154 | // Dump all the relations known to file F. | |
1155 | ||
1156 | void | |
1157 | relation_oracle::dump (FILE *f) const | |
1158 | { | |
1159 | fprintf (f, "Relation dump\n"); | |
1160 | for (unsigned i = 0; i < m_relations.length (); i++) | |
ce0b409f AM |
1161 | if (BASIC_BLOCK_FOR_FN (cfun, i)) |
1162 | { | |
1163 | fprintf (f, "BB%d\n", i); | |
1164 | dump (f, BASIC_BLOCK_FOR_FN (cfun, i)); | |
1165 | } | |
3aaa69e5 | 1166 | } |