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