]>
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 | ||
115 | // Intersect relation R! with relation R2 and return the resulting relation. | |
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 | ||
158 | // ------------------------------------------------------------------------- | |
159 | ||
160 | // This class represents an equivalency set, and contains a link to the next | |
161 | // one in the list to be searched. | |
162 | ||
163 | // The very first element in the m_equiv chain is actually just a summary | |
164 | // element in which the m_names bitmap is used to indicate that an ssa_name | |
165 | // has an equivalence set in this block. | |
166 | // This allows for much faster traversal of the DOM chain, as a search for | |
167 | // SSA_NAME simply requires walking the DOM chain until a block is found | |
168 | // which has the bit for SSA_NAME set. Then scan for the equivalency set in | |
169 | // that block. No previous blcoks need be searched. | |
170 | ||
171 | class equiv_chain | |
172 | { | |
173 | public: | |
174 | bitmap m_names; // ssa-names in equiv set. | |
175 | basic_block m_bb; // Block this belongs to | |
176 | equiv_chain *m_next; // Next in block list. | |
177 | void dump (FILE *f) const; // Show names in this list. | |
178 | }; | |
179 | ||
180 | ||
181 | // Dump the names in this equivalence set. | |
182 | ||
183 | void | |
184 | equiv_chain::dump (FILE *f) const | |
185 | { | |
186 | bitmap_iterator bi; | |
187 | unsigned i; | |
188 | ||
189 | if (!m_names) | |
190 | return; | |
191 | fprintf (f, "Equivalence set : ["); | |
192 | unsigned c = 0; | |
193 | EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi) | |
194 | { | |
195 | if (ssa_name (i)) | |
196 | { | |
197 | if (c++) | |
198 | fprintf (f, ", "); | |
199 | print_generic_expr (f, ssa_name (i), TDF_SLIM); | |
200 | } | |
201 | } | |
202 | fprintf (f, "]\n"); | |
203 | } | |
204 | ||
205 | // Instantiate an equivalency oracle. | |
206 | ||
207 | equiv_oracle::equiv_oracle () | |
208 | { | |
209 | bitmap_obstack_initialize (&m_bitmaps); | |
210 | m_equiv.create (0); | |
211 | m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
212 | m_equiv_set = BITMAP_ALLOC (&m_bitmaps); | |
213 | obstack_init (&m_chain_obstack); | |
214 | } | |
215 | ||
216 | // Destruct an equivalency oracle. | |
217 | ||
218 | equiv_oracle::~equiv_oracle () | |
219 | { | |
220 | obstack_free (&m_chain_obstack, NULL); | |
221 | m_equiv.release (); | |
222 | bitmap_obstack_release (&m_bitmaps); | |
223 | } | |
224 | ||
225 | // Find and return the equivalency set for SSA along the dominators of BB. | |
226 | // This is the external API. | |
227 | ||
228 | const_bitmap | |
229 | equiv_oracle::equiv_set (tree ssa, basic_block bb) const | |
230 | { | |
231 | // Search the dominator tree for an equivalency. | |
232 | equiv_chain *equiv = find_equiv_dom (ssa, bb); | |
233 | if (equiv) | |
234 | return equiv->m_names; | |
235 | ||
236 | return NULL; | |
237 | } | |
238 | ||
239 | ||
240 | // If SSA has an equivalence in block BB, find and return it. | |
241 | // Otherwise return NULL. | |
242 | ||
243 | equiv_chain * | |
244 | equiv_oracle::find_equiv_block (unsigned ssa, int bb) const | |
245 | { | |
246 | equiv_chain *ptr = NULL; | |
247 | if (bb >= (int)m_equiv.length ()) | |
248 | return NULL; | |
249 | ||
250 | // If there are equiv sets and SSA is in one in this block, find it. | |
251 | // Otherwise return NULL. | |
252 | if (m_equiv[bb] && bitmap_bit_p (m_equiv[bb]->m_names, ssa)) | |
253 | { | |
254 | for (ptr = m_equiv[bb]->m_next; ptr; ptr = ptr->m_next) | |
255 | if (bitmap_bit_p (ptr->m_names, ssa)) | |
256 | break; | |
257 | } | |
258 | return ptr; | |
259 | } | |
260 | ||
261 | // Starting at block BB, walk the dominator chain looking for the nearest | |
262 | // equivalence set containing NAME. | |
263 | ||
264 | equiv_chain * | |
265 | equiv_oracle::find_equiv_dom (tree name, basic_block bb) const | |
266 | { | |
267 | unsigned v = SSA_NAME_VERSION (name); | |
268 | // Short circuit looking for names which have no equivalences. | |
269 | // Saves time looking for something which does not exist. | |
270 | if (!bitmap_bit_p (m_equiv_set, v)) | |
271 | return NULL; | |
272 | ||
273 | // NAME has at least once equivalence set, check to see if it has one along | |
274 | // the dominator tree. | |
275 | for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
276 | { | |
277 | equiv_chain *ptr = find_equiv_block (v, bb->index); | |
278 | if (ptr) | |
279 | return ptr; | |
280 | } | |
281 | return NULL; | |
282 | } | |
283 | ||
284 | // Register equivalance between ssa_name V and set EQUIV in block BB, | |
285 | ||
286 | bitmap | |
287 | equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv) | |
288 | { | |
289 | // V will have an equivalency now. | |
290 | bitmap_set_bit (m_equiv_set, v); | |
291 | ||
292 | // If that equiv chain is in this block, simply use it. | |
293 | if (equiv->m_bb == bb) | |
294 | { | |
295 | bitmap_set_bit (equiv->m_names, v); | |
296 | bitmap_set_bit (m_equiv[bb->index]->m_names, v); | |
297 | return NULL; | |
298 | } | |
299 | ||
300 | // Otherwise create an equivalence for this block which is a copy | |
301 | // of equiv, the add V to the set. | |
302 | bitmap b = BITMAP_ALLOC (&m_bitmaps); | |
303 | bitmap_copy (b, equiv->m_names); | |
304 | bitmap_set_bit (b, v); | |
305 | return b; | |
306 | } | |
307 | ||
308 | // Register equivalence between set equiv_1 and equiv_2 in block BB. | |
309 | // Return NULL if either name can be merged with the other. Otherwise | |
310 | // return a pointer to the combined bitmap of names. This allows the | |
311 | // caller to do any setup required for a new element. | |
312 | ||
313 | bitmap | |
314 | equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1, | |
315 | equiv_chain *equiv_2) | |
316 | { | |
317 | // If equiv_1 is alreayd in BB, use it as the combined set. | |
318 | if (equiv_1->m_bb == bb) | |
319 | { | |
320 | bitmap_ior_into (equiv_1->m_names, equiv_2->m_names); | |
321 | // Its hard to delete from a single linked list, so | |
322 | // just clear the second one. | |
323 | if (equiv_2->m_bb == bb) | |
324 | bitmap_clear (equiv_2->m_names); | |
325 | else | |
326 | // Ensure equiv_2s names are in the summary for BB. | |
327 | bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names); | |
328 | return NULL; | |
329 | } | |
330 | // If equiv_2 is in BB, use it for the combined set. | |
331 | if (equiv_2->m_bb == bb) | |
332 | { | |
333 | bitmap_ior_into (equiv_2->m_names, equiv_1->m_names); | |
334 | // Add equiv_1 names into the summary. | |
335 | bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names); | |
336 | return NULL; | |
337 | } | |
338 | ||
339 | // At this point, neither equivalence is from this block. | |
340 | bitmap b = BITMAP_ALLOC (&m_bitmaps); | |
341 | bitmap_copy (b, equiv_1->m_names); | |
342 | bitmap_ior_into (b, equiv_2->m_names); | |
343 | return b; | |
344 | } | |
345 | ||
346 | ||
347 | // Register an equivalence between SSA1 and SSA2 in block BB. | |
348 | // The equivalence oracle maintains a vector of equivalencies indexed by basic | |
349 | // block. When an equivalence bteween SSA1 and SSA2 is registered in block BB, | |
350 | // a query is made as to what equivalences both names have already, and | |
351 | // any preexisting equivalences are merged to create a single equivalence | |
352 | // containing all the ssa_names in this basic block. | |
353 | ||
354 | void | |
355 | equiv_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2) | |
356 | { | |
357 | unsigned v1 = SSA_NAME_VERSION (ssa1); | |
358 | unsigned v2 = SSA_NAME_VERSION (ssa2); | |
359 | equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb); | |
360 | equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb); | |
361 | ||
362 | // Check if they are the same set | |
363 | if (equiv_1 && equiv_1 == equiv_2) | |
364 | return; | |
365 | ||
366 | bitmap equiv_set; | |
367 | ||
368 | // Case where we have 2 SSA_NAMEs that are not in any set. | |
369 | if (!equiv_1 && !equiv_2) | |
370 | { | |
371 | bitmap_set_bit (m_equiv_set, v1); | |
372 | bitmap_set_bit (m_equiv_set, v2); | |
373 | ||
374 | equiv_set = BITMAP_ALLOC (&m_bitmaps); | |
375 | bitmap_set_bit (equiv_set, v1); | |
376 | bitmap_set_bit (equiv_set, v2); | |
377 | } | |
378 | else if (!equiv_1 && equiv_2) | |
379 | equiv_set = register_equiv (bb, v1, equiv_2); | |
380 | else if (equiv_1 && !equiv_2) | |
381 | equiv_set = register_equiv (bb, v2, equiv_1); | |
382 | else | |
383 | equiv_set = register_equiv (bb, equiv_1, equiv_2); | |
384 | ||
385 | // A non-null return is a bitmap that is to be added to the current | |
386 | // block as a new equivalence. | |
387 | if (!equiv_set) | |
388 | return; | |
389 | ||
390 | equiv_chain *ptr; | |
391 | ||
392 | // Check if this is the first time a block has an equivalence added. | |
393 | // and create a header block. And set the summary for this block. | |
394 | if (!m_equiv[bb->index]) | |
395 | { | |
396 | ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, | |
397 | sizeof (equiv_chain)); | |
398 | ptr->m_names = BITMAP_ALLOC (&m_bitmaps); | |
399 | bitmap_copy (ptr->m_names, equiv_set); | |
400 | ptr->m_bb = bb; | |
401 | ptr->m_next = NULL; | |
402 | m_equiv[bb->index] = ptr; | |
403 | } | |
404 | ||
405 | // Now create the element for this equiv set and initialize it. | |
406 | ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain)); | |
407 | ptr->m_names = equiv_set; | |
408 | ptr->m_bb = bb; | |
409 | gcc_checking_assert (bb->index < (int)m_equiv.length ()); | |
410 | ptr->m_next = m_equiv[bb->index]->m_next; | |
411 | m_equiv[bb->index]->m_next = ptr; | |
412 | bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set); | |
413 | } | |
414 | ||
415 | // Make sure the BB vector is big enough and grow it if needed. | |
416 | ||
417 | void | |
418 | equiv_oracle::limit_check (basic_block bb) | |
419 | { | |
420 | int i = (bb) ? bb->index : last_basic_block_for_fn (cfun); | |
421 | if (i >= (int)m_equiv.length ()) | |
422 | m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
423 | } | |
424 | ||
425 | // Dump the equivalence sets in BB to file F. | |
426 | ||
427 | void | |
428 | equiv_oracle::dump (FILE *f, basic_block bb) const | |
429 | { | |
430 | if (bb->index >= (int)m_equiv.length ()) | |
431 | return; | |
432 | if (!m_equiv[bb->index]) | |
433 | return; | |
434 | ||
435 | equiv_chain *ptr = m_equiv[bb->index]->m_next; | |
436 | for (; ptr; ptr = ptr->m_next) | |
437 | ptr->dump (f); | |
438 | } | |
439 | ||
440 | // Dump all equivalence sets known to the oracle. | |
441 | ||
442 | void | |
443 | equiv_oracle::dump (FILE *f) const | |
444 | { | |
445 | fprintf (f, "Equivalency dump\n"); | |
446 | for (unsigned i = 0; i < m_equiv.length (); i++) | |
447 | if (m_equiv[i]) | |
448 | { | |
449 | fprintf (f, "BB%d\n", i); | |
450 | dump (f, BASIC_BLOCK_FOR_FN (cfun, i)); | |
451 | } | |
452 | } | |
453 | ||
454 | ||
455 | // -------------------------------------------------------------------------- | |
456 | ||
457 | // The value-relation class is used to encapsulate the represention of an | |
458 | // individual relation between 2 ssa-names, and to facilitate operating on | |
459 | // the relation. | |
460 | ||
461 | class value_relation | |
462 | { | |
463 | public: | |
464 | value_relation (); | |
465 | value_relation (relation_kind kind, tree n1, tree n2); | |
466 | void set_relation (relation_kind kind, tree n1, tree n2); | |
467 | ||
468 | inline relation_kind kind () const { return related; } | |
469 | inline tree op1 () const { return name1; } | |
470 | inline tree op2 () const { return name2; } | |
471 | ||
472 | bool union_ (value_relation &p); | |
473 | bool intersect (value_relation &p); | |
474 | void negate (); | |
475 | void swap (); | |
476 | ||
477 | void dump (FILE *f) const; | |
478 | private: | |
479 | relation_kind related; | |
480 | tree name1, name2; | |
481 | }; | |
482 | ||
483 | // Set relation R between ssa_name N1 and N2. | |
484 | ||
485 | inline void | |
486 | value_relation::set_relation (relation_kind r, tree n1, tree n2) | |
487 | { | |
488 | gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2)); | |
489 | related = r; | |
490 | name1 = n1; | |
491 | name2 = n2; | |
492 | } | |
493 | ||
494 | // Default constructor. | |
495 | ||
496 | inline | |
497 | value_relation::value_relation () | |
498 | { | |
499 | related = VREL_NONE; | |
500 | name1 = NULL_TREE; | |
501 | name2 = NULL_TREE; | |
502 | } | |
503 | ||
504 | // Constructor for relation R between SSA version N1 nd N2. | |
505 | ||
506 | inline | |
507 | value_relation::value_relation (relation_kind kind, tree n1, tree n2) | |
508 | { | |
509 | set_relation (kind, n1, n2); | |
510 | } | |
511 | ||
512 | // Negate the current relation. | |
513 | ||
514 | void | |
515 | value_relation::negate () | |
516 | { | |
517 | related = relation_negate (related); | |
518 | } | |
519 | ||
520 | // Modify the relation as if the operands were being swapped. | |
521 | ||
522 | void | |
523 | value_relation::swap () | |
524 | { | |
525 | related = relation_swap (related); | |
526 | } | |
527 | ||
528 | // Perform an intersection between 2 relations. *this &&= p. | |
529 | ||
530 | bool | |
531 | value_relation::intersect (value_relation &p) | |
532 | { | |
533 | // Save previous value | |
534 | relation_kind old = related; | |
535 | ||
536 | if (p.op1 () == op1 () && p.op2 () == op2 ()) | |
537 | related = relation_intersect (kind (), p.kind ()); | |
538 | else if (p.op2 () == op1 () && p.op1 () == op2 ()) | |
539 | related = relation_intersect (kind (), relation_swap (p.kind ())); | |
540 | else | |
541 | return false; | |
542 | ||
543 | return old != related; | |
544 | } | |
545 | ||
546 | // Perform a union between 2 relations. *this ||= p. | |
547 | ||
548 | bool | |
549 | value_relation::union_ (value_relation &p) | |
550 | { | |
551 | // Save previous value | |
552 | relation_kind old = related; | |
553 | ||
554 | if (p.op1 () == op1 () && p.op2 () == op2 ()) | |
555 | related = relation_union (kind(), p.kind()); | |
556 | else if (p.op2 () == op1 () && p.op1 () == op2 ()) | |
557 | related = relation_union (kind(), relation_swap (p.kind ())); | |
558 | else | |
559 | return false; | |
560 | ||
561 | return old != related; | |
562 | } | |
563 | ||
564 | ||
565 | // Dump the relation to file F. | |
566 | ||
567 | void | |
568 | value_relation::dump (FILE *f) const | |
569 | { | |
570 | if (!name1 || !name2) | |
571 | { | |
572 | fprintf (f, "uninitialized"); | |
573 | return; | |
574 | } | |
575 | fputc ('(', f); | |
576 | print_generic_expr (f, op1 (), TDF_SLIM); | |
577 | print_relation (f, kind ()); | |
578 | print_generic_expr (f, op2 (), TDF_SLIM); | |
579 | fputc(')', f); | |
580 | } | |
581 | ||
582 | // This container is used to link relations in a chain. | |
583 | ||
584 | class relation_chain : public value_relation | |
585 | { | |
586 | public: | |
587 | relation_chain *m_next; | |
588 | }; | |
589 | ||
590 | // ------------------------------------------------------------------------ | |
591 | ||
592 | // Instantiate a relation oracle. | |
593 | ||
594 | relation_oracle::relation_oracle () | |
595 | { | |
596 | m_relations.create (0); | |
597 | m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
598 | m_relation_set = BITMAP_ALLOC (&m_bitmaps); | |
599 | m_tmp = BITMAP_ALLOC (&m_bitmaps); | |
600 | } | |
601 | ||
602 | // Destruct a relation oracle. | |
603 | ||
604 | relation_oracle::~relation_oracle () | |
605 | { | |
606 | m_relations.release (); | |
607 | } | |
608 | ||
609 | // Register relation K between ssa_name OP1 and OP2 on STMT. | |
610 | ||
611 | void | |
612 | relation_oracle::register_relation (gimple *stmt, relation_kind k, tree op1, | |
613 | tree op2) | |
614 | { | |
615 | gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); | |
616 | gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); | |
617 | gcc_checking_assert (stmt && gimple_bb (stmt)); | |
618 | ||
619 | // Don't register lack of a relation. | |
620 | if (k == VREL_NONE) | |
621 | return; | |
622 | ||
623 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
624 | { | |
625 | value_relation vr (k, op1, op2); | |
626 | fprintf (dump_file, " Registering value_relation "); | |
627 | vr.dump (dump_file); | |
628 | fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index); | |
629 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
630 | } | |
631 | ||
632 | // This relation applies to the entire block, use STMT's block. | |
633 | // Equivalencies are handled by the equivalence oracle. | |
634 | if (k == EQ_EXPR) | |
635 | register_equiv (gimple_bb (stmt), op1, op2); | |
636 | else | |
637 | register_relation (gimple_bb (stmt), k, op1, op2); | |
638 | } | |
639 | ||
640 | // Register relation K between ssa_name OP1 and OP2 on edge E. | |
641 | ||
642 | void | |
643 | relation_oracle::register_relation (edge e, relation_kind k, tree op1, | |
644 | tree op2) | |
645 | { | |
646 | gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); | |
647 | gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); | |
648 | ||
649 | // Do not register lack of relation, or blocks which have more than | |
650 | // edge E for a predecessor. | |
651 | if (k == VREL_NONE || !single_pred_p (e->dest)) | |
652 | return; | |
653 | ||
654 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
655 | { | |
656 | value_relation vr (k, op1, op2); | |
657 | fprintf (dump_file, " Registering value_relation "); | |
658 | vr.dump (dump_file); | |
659 | fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index); | |
660 | } | |
661 | ||
662 | // Equivalencies are handled by the equivalence oracle. | |
663 | if (k == EQ_EXPR) | |
664 | register_equiv (e->dest, op1, op2); | |
665 | else | |
666 | register_relation (e->dest, k, op1, op2); | |
667 | } | |
668 | ||
669 | // Register relation K between OP! and OP2 in block BB. | |
670 | // This creates the record and searches for existing records in the dominator | |
671 | // tree to merge with. | |
672 | ||
673 | void | |
674 | relation_oracle::register_relation (basic_block bb, relation_kind k, tree op1, | |
675 | tree op2) | |
676 | { | |
677 | gcc_checking_assert (k != VREL_NONE); | |
678 | ||
679 | value_relation vr(k, op1, op2); | |
680 | int bbi = bb->index; | |
681 | ||
682 | if (bbi >= (int)m_relations.length()) | |
683 | m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
684 | ||
685 | // Summary bitmap indicating what ssa_names have relations in this BB. | |
686 | bitmap bm = m_relations[bbi].m_names; | |
687 | if (!bm) | |
688 | bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps); | |
689 | unsigned v1 = SSA_NAME_VERSION (op1); | |
690 | unsigned v2 = SSA_NAME_VERSION (op2); | |
691 | ||
692 | relation_kind curr; | |
693 | relation_chain *ptr; | |
694 | curr = find_relation_block (bbi, v1, v2, &ptr); | |
695 | // There is an existing relation in this block, just intersect with it. | |
696 | if (curr != VREL_NONE) | |
697 | { | |
698 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
699 | { | |
700 | fprintf (dump_file, " Intersecting with existing "); | |
701 | ptr->dump (dump_file); | |
702 | } | |
703 | // Check into whether we can simply replace the relation rather than | |
704 | // intersecting it. THis may help with some optimistic iterative | |
705 | // updating algorithms. | |
706 | ptr->intersect (vr); | |
707 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
708 | { | |
709 | fprintf (dump_file, " to produce "); | |
710 | ptr->dump (dump_file); | |
711 | fprintf (dump_file, "\n"); | |
712 | } | |
713 | return; | |
714 | } | |
715 | ||
716 | // Check for an existing relation further up the DOM chain. | |
717 | // By including dominating relations, The first one found in any search | |
718 | // will be the aggregate of all the previous ones. | |
719 | curr = find_relation_dom (bb, v1, v2); | |
720 | if (curr != VREL_NONE) | |
721 | k = relation_intersect (curr, k); | |
722 | ||
723 | bitmap_set_bit (bm, v1); | |
724 | bitmap_set_bit (bm, v2); | |
725 | bitmap_set_bit (m_relation_set, v1); | |
726 | bitmap_set_bit (m_relation_set, v2); | |
727 | ||
728 | ptr = (relation_chain *) obstack_alloc (&m_chain_obstack, | |
729 | sizeof (relation_chain)); | |
730 | ptr->set_relation (k, op1, op2); | |
731 | ptr->m_next = m_relations[bbi].m_head; | |
732 | m_relations[bbi].m_head = ptr;; | |
733 | } | |
734 | ||
735 | // Find the relation between any ssa_name in B1 and any name in B2 in block BB. | |
736 | // This will allow equivalencies to be applied to any SSA_NAME in a relation. | |
737 | ||
738 | relation_kind | |
739 | relation_oracle::find_relation_block (unsigned bb, const_bitmap b1, | |
740 | const_bitmap b2) | |
741 | { | |
742 | const_bitmap bm; | |
743 | if (bb >= m_relations.length()) | |
744 | return VREL_NONE; | |
745 | ||
746 | bm = m_relations[bb].m_names; | |
747 | if (!bm) | |
748 | return VREL_NONE; | |
749 | ||
750 | // If both b1 and b2 aren't referenced in thie block, cant be a relation | |
751 | if (!bitmap_intersect_p (bm, b1) || !bitmap_intersect_p (bm, b2)) | |
752 | return VREL_NONE; | |
753 | ||
754 | // Search for the fiorst relation that contains BOTH an element from B1 | |
755 | // and B2, and return that relation. | |
756 | for (relation_chain *ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next) | |
757 | { | |
758 | unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); | |
759 | unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); | |
760 | if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b1, op2)) | |
761 | return ptr->kind (); | |
762 | if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b1, op1)) | |
763 | return relation_swap (ptr->kind ()); | |
764 | } | |
765 | ||
766 | return VREL_NONE; | |
767 | } | |
768 | ||
769 | // Search the DOM tree for a relation between an element of B1 and B2, starting | |
770 | // with block BB. | |
771 | ||
772 | relation_kind | |
773 | relation_oracle::find_relation_dom (basic_block bb, const_bitmap b1, | |
774 | const_bitmap b2) | |
775 | { | |
776 | relation_kind r; | |
777 | // If either name does not occur in a relation anywhere, there isnt one. | |
778 | if (!bitmap_intersect_p (m_relation_set, b1) | |
779 | || !bitmap_intersect_p (m_relation_set, b2)) | |
780 | return VREL_NONE; | |
781 | ||
782 | // Search each block in the DOM tree checking. | |
783 | for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
784 | { | |
785 | r = find_relation_block (bb->index, b1, b2); | |
786 | if (r != VREL_NONE) | |
787 | return r; | |
788 | } | |
789 | return VREL_NONE; | |
790 | ||
791 | } | |
792 | ||
793 | // Find a relation in block BB between ssa version V1 and V2. If a relation | |
794 | // is found, return a pointer to the chain object in OBJ. | |
795 | ||
796 | relation_kind | |
797 | relation_oracle::find_relation_block (int bb, unsigned v1, unsigned v2, | |
798 | relation_chain **obj) | |
799 | { | |
800 | if (bb >= (int)m_relations.length()) | |
801 | return VREL_NONE; | |
802 | ||
803 | const_bitmap bm = m_relations[bb].m_names; | |
804 | if (!bm) | |
805 | return VREL_NONE; | |
806 | ||
807 | // If both b1 and b2 aren't referenced in thie block, cant be a relation | |
808 | if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2)) | |
809 | return VREL_NONE; | |
810 | ||
811 | relation_chain *ptr; | |
812 | for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next) | |
813 | { | |
814 | unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); | |
815 | unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); | |
816 | if (v1 == op1 && v2 == op2) | |
817 | { | |
818 | if (obj) | |
819 | *obj = ptr; | |
820 | return ptr->kind (); | |
821 | } | |
822 | if (v1 == op2 && v2 == op1) | |
823 | { | |
824 | if (obj) | |
825 | *obj = ptr; | |
826 | return relation_swap (ptr->kind ()); | |
827 | } | |
828 | } | |
829 | ||
830 | return VREL_NONE; | |
831 | } | |
832 | ||
833 | // Find a relation between SSA version V1 and V2 in the dominator tree | |
834 | // starting with block BB | |
835 | ||
836 | relation_kind | |
837 | relation_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) | |
838 | { | |
839 | relation_kind r; | |
840 | // IF either name does not occur in a relation anywhere, there isnt one. | |
841 | if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2)) | |
842 | return VREL_NONE; | |
843 | ||
844 | for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
845 | { | |
846 | r = find_relation_block (bb->index, v1, v2); | |
847 | if (r != VREL_NONE) | |
848 | return r; | |
849 | } | |
850 | return VREL_NONE; | |
851 | ||
852 | } | |
853 | ||
854 | // Query if there is a relation between SSA1 and SS2 in block BB or a | |
855 | // dominator of BB | |
856 | ||
857 | relation_kind | |
858 | relation_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) | |
859 | { | |
860 | relation_kind kind; | |
861 | unsigned v1 = SSA_NAME_VERSION (ssa1); | |
862 | unsigned v2 = SSA_NAME_VERSION (ssa2); | |
863 | if (v1 == v2) | |
864 | return EQ_EXPR; | |
865 | ||
866 | // Check for equivalence first. | |
867 | const_bitmap equiv1 = equiv_set (ssa1, bb); | |
868 | if (equiv1 && bitmap_bit_p (equiv1, v2)) | |
869 | return EQ_EXPR; | |
870 | ||
871 | // Initially look for a direct relationship and just return that. | |
872 | kind = find_relation_dom (bb, v1, v2); | |
873 | if (kind != VREL_NONE) | |
874 | return kind; | |
875 | ||
876 | // If one is not found, see if there is a relationship between equivalences. | |
877 | // If v2 isn't in v1s equiv set, then v1 shouldn't be in v2's set either. | |
878 | const_bitmap equiv2 = equiv_set (ssa2, bb); | |
879 | gcc_checking_assert (!equiv2 || !bitmap_bit_p (equiv2, v1)); | |
880 | ||
881 | if (!equiv1 && !equiv2) | |
882 | kind = VREL_NONE; | |
883 | else if (!equiv1) | |
884 | { | |
885 | bitmap_clear (m_tmp); | |
886 | bitmap_set_bit (m_tmp, v1); | |
887 | kind = find_relation_dom (bb, m_tmp, equiv2); | |
888 | } | |
889 | else if (!equiv2) | |
890 | { | |
891 | bitmap_clear (m_tmp); | |
892 | bitmap_set_bit (m_tmp, v2); | |
893 | kind = find_relation_dom (bb, equiv1, m_tmp); | |
894 | } | |
895 | else | |
896 | kind = find_relation_dom (bb, equiv1, equiv2); | |
897 | return kind; | |
898 | } | |
899 | ||
900 | // Dump all the relations in block BB to file F. | |
901 | ||
902 | void | |
903 | relation_oracle::dump (FILE *f, basic_block bb) const | |
904 | { | |
905 | equiv_oracle::dump (f,bb); | |
906 | ||
907 | if (bb->index >= (int)m_relations.length ()) | |
908 | return; | |
909 | if (!m_relations[bb->index].m_names) | |
910 | return; | |
911 | ||
912 | relation_chain *ptr = m_relations[bb->index].m_head; | |
913 | for (; ptr; ptr = ptr->m_next) | |
914 | { | |
915 | fprintf (f, "Relational : "); | |
916 | ptr->dump (f); | |
917 | fprintf (f, "\n"); | |
918 | } | |
919 | } | |
920 | ||
921 | // Dump all the relations known to file F. | |
922 | ||
923 | void | |
924 | relation_oracle::dump (FILE *f) const | |
925 | { | |
926 | fprintf (f, "Relation dump\n"); | |
927 | for (unsigned i = 0; i < m_relations.length (); i++) | |
928 | { | |
929 | fprintf (f, "BB%d\n", i); | |
930 | dump (f, BASIC_BLOCK_FOR_FN (cfun, i)); | |
931 | } | |
932 | } |