]>
Commit | Line | Data |
---|---|---|
3aaa69e5 | 1 | /* Header file for the value range relational processing. |
7adcbafe | 2 | Copyright (C) 2020-2022 Free Software Foundation, Inc. |
3aaa69e5 AM |
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 | ||
5d110fe9 AM |
410 | // Create an equivalency set containing only SSA in its definition block. |
411 | // This is done the first time SSA is registered in an equivalency and blocks | |
412 | // any DOM searches past the definition. | |
413 | ||
414 | void | |
415 | equiv_oracle::register_initial_def (tree ssa) | |
416 | { | |
417 | if (SSA_NAME_IS_DEFAULT_DEF (ssa)) | |
418 | return; | |
419 | basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa)); | |
420 | gcc_checking_assert (bb && !find_equiv_dom (ssa, bb)); | |
421 | ||
422 | unsigned v = SSA_NAME_VERSION (ssa); | |
423 | bitmap_set_bit (m_equiv_set, v); | |
424 | bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps); | |
425 | bitmap_set_bit (equiv_set, v); | |
426 | add_equiv_to_block (bb, equiv_set); | |
427 | } | |
3aaa69e5 AM |
428 | |
429 | // Register an equivalence between SSA1 and SSA2 in block BB. | |
430 | // The equivalence oracle maintains a vector of equivalencies indexed by basic | |
431 | // block. When an equivalence bteween SSA1 and SSA2 is registered in block BB, | |
432 | // a query is made as to what equivalences both names have already, and | |
433 | // any preexisting equivalences are merged to create a single equivalence | |
434 | // containing all the ssa_names in this basic block. | |
435 | ||
436 | void | |
3674d8e6 AM |
437 | equiv_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1, |
438 | tree ssa2) | |
3aaa69e5 | 439 | { |
3674d8e6 AM |
440 | // Only handle equality relations. |
441 | if (k != EQ_EXPR) | |
442 | return; | |
443 | ||
3aaa69e5 AM |
444 | unsigned v1 = SSA_NAME_VERSION (ssa1); |
445 | unsigned v2 = SSA_NAME_VERSION (ssa2); | |
5d110fe9 AM |
446 | |
447 | // If this is the first time an ssa_name has an equivalency registered | |
448 | // create a self-equivalency record in the def block. | |
449 | if (!bitmap_bit_p (m_equiv_set, v1)) | |
450 | register_initial_def (ssa1); | |
451 | if (!bitmap_bit_p (m_equiv_set, v2)) | |
452 | register_initial_def (ssa2); | |
453 | ||
3aaa69e5 AM |
454 | equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb); |
455 | equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb); | |
456 | ||
457 | // Check if they are the same set | |
458 | if (equiv_1 && equiv_1 == equiv_2) | |
459 | return; | |
460 | ||
461 | bitmap equiv_set; | |
462 | ||
463 | // Case where we have 2 SSA_NAMEs that are not in any set. | |
464 | if (!equiv_1 && !equiv_2) | |
465 | { | |
466 | bitmap_set_bit (m_equiv_set, v1); | |
467 | bitmap_set_bit (m_equiv_set, v2); | |
468 | ||
469 | equiv_set = BITMAP_ALLOC (&m_bitmaps); | |
470 | bitmap_set_bit (equiv_set, v1); | |
471 | bitmap_set_bit (equiv_set, v2); | |
472 | } | |
473 | else if (!equiv_1 && equiv_2) | |
474 | equiv_set = register_equiv (bb, v1, equiv_2); | |
475 | else if (equiv_1 && !equiv_2) | |
476 | equiv_set = register_equiv (bb, v2, equiv_1); | |
477 | else | |
478 | equiv_set = register_equiv (bb, equiv_1, equiv_2); | |
479 | ||
480 | // A non-null return is a bitmap that is to be added to the current | |
481 | // block as a new equivalence. | |
482 | if (!equiv_set) | |
483 | return; | |
484 | ||
5d110fe9 AM |
485 | add_equiv_to_block (bb, equiv_set); |
486 | } | |
487 | ||
488 | // Add an equivalency record in block BB containing bitmap EQUIV_SET. | |
489 | // Note the internal caller is responible for allocating EQUIV_SET properly. | |
490 | ||
491 | void | |
492 | equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set) | |
493 | { | |
3aaa69e5 AM |
494 | equiv_chain *ptr; |
495 | ||
496 | // Check if this is the first time a block has an equivalence added. | |
497 | // and create a header block. And set the summary for this block. | |
498 | if (!m_equiv[bb->index]) | |
499 | { | |
500 | ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, | |
501 | sizeof (equiv_chain)); | |
502 | ptr->m_names = BITMAP_ALLOC (&m_bitmaps); | |
503 | bitmap_copy (ptr->m_names, equiv_set); | |
504 | ptr->m_bb = bb; | |
505 | ptr->m_next = NULL; | |
506 | m_equiv[bb->index] = ptr; | |
507 | } | |
508 | ||
509 | // Now create the element for this equiv set and initialize it. | |
510 | ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain)); | |
511 | ptr->m_names = equiv_set; | |
512 | ptr->m_bb = bb; | |
513 | gcc_checking_assert (bb->index < (int)m_equiv.length ()); | |
514 | ptr->m_next = m_equiv[bb->index]->m_next; | |
515 | m_equiv[bb->index]->m_next = ptr; | |
516 | bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set); | |
517 | } | |
518 | ||
519 | // Make sure the BB vector is big enough and grow it if needed. | |
520 | ||
521 | void | |
522 | equiv_oracle::limit_check (basic_block bb) | |
523 | { | |
524 | int i = (bb) ? bb->index : last_basic_block_for_fn (cfun); | |
525 | if (i >= (int)m_equiv.length ()) | |
526 | m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
527 | } | |
528 | ||
529 | // Dump the equivalence sets in BB to file F. | |
530 | ||
531 | void | |
532 | equiv_oracle::dump (FILE *f, basic_block bb) const | |
533 | { | |
534 | if (bb->index >= (int)m_equiv.length ()) | |
535 | return; | |
536 | if (!m_equiv[bb->index]) | |
537 | return; | |
538 | ||
539 | equiv_chain *ptr = m_equiv[bb->index]->m_next; | |
540 | for (; ptr; ptr = ptr->m_next) | |
541 | ptr->dump (f); | |
542 | } | |
543 | ||
544 | // Dump all equivalence sets known to the oracle. | |
545 | ||
546 | void | |
547 | equiv_oracle::dump (FILE *f) const | |
548 | { | |
549 | fprintf (f, "Equivalency dump\n"); | |
550 | for (unsigned i = 0; i < m_equiv.length (); i++) | |
ce0b409f | 551 | if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i)) |
3aaa69e5 AM |
552 | { |
553 | fprintf (f, "BB%d\n", i); | |
554 | dump (f, BASIC_BLOCK_FOR_FN (cfun, i)); | |
555 | } | |
556 | } | |
557 | ||
558 | ||
559 | // -------------------------------------------------------------------------- | |
560 | ||
561 | // The value-relation class is used to encapsulate the represention of an | |
562 | // individual relation between 2 ssa-names, and to facilitate operating on | |
563 | // the relation. | |
564 | ||
565 | class value_relation | |
566 | { | |
567 | public: | |
568 | value_relation (); | |
569 | value_relation (relation_kind kind, tree n1, tree n2); | |
570 | void set_relation (relation_kind kind, tree n1, tree n2); | |
571 | ||
572 | inline relation_kind kind () const { return related; } | |
573 | inline tree op1 () const { return name1; } | |
574 | inline tree op2 () const { return name2; } | |
575 | ||
576 | bool union_ (value_relation &p); | |
577 | bool intersect (value_relation &p); | |
578 | void negate (); | |
675a3e40 | 579 | bool apply_transitive (const value_relation &rel); |
3aaa69e5 AM |
580 | |
581 | void dump (FILE *f) const; | |
582 | private: | |
583 | relation_kind related; | |
584 | tree name1, name2; | |
585 | }; | |
586 | ||
587 | // Set relation R between ssa_name N1 and N2. | |
588 | ||
589 | inline void | |
590 | value_relation::set_relation (relation_kind r, tree n1, tree n2) | |
591 | { | |
592 | gcc_checking_assert (SSA_NAME_VERSION (n1) != SSA_NAME_VERSION (n2)); | |
593 | related = r; | |
594 | name1 = n1; | |
595 | name2 = n2; | |
596 | } | |
597 | ||
598 | // Default constructor. | |
599 | ||
600 | inline | |
601 | value_relation::value_relation () | |
602 | { | |
603 | related = VREL_NONE; | |
604 | name1 = NULL_TREE; | |
605 | name2 = NULL_TREE; | |
606 | } | |
607 | ||
608 | // Constructor for relation R between SSA version N1 nd N2. | |
609 | ||
610 | inline | |
611 | value_relation::value_relation (relation_kind kind, tree n1, tree n2) | |
612 | { | |
613 | set_relation (kind, n1, n2); | |
614 | } | |
615 | ||
616 | // Negate the current relation. | |
617 | ||
618 | void | |
619 | value_relation::negate () | |
620 | { | |
621 | related = relation_negate (related); | |
622 | } | |
623 | ||
3aaa69e5 AM |
624 | // Perform an intersection between 2 relations. *this &&= p. |
625 | ||
626 | bool | |
627 | value_relation::intersect (value_relation &p) | |
628 | { | |
629 | // Save previous value | |
630 | relation_kind old = related; | |
631 | ||
632 | if (p.op1 () == op1 () && p.op2 () == op2 ()) | |
633 | related = relation_intersect (kind (), p.kind ()); | |
634 | else if (p.op2 () == op1 () && p.op1 () == op2 ()) | |
635 | related = relation_intersect (kind (), relation_swap (p.kind ())); | |
636 | else | |
637 | return false; | |
638 | ||
639 | return old != related; | |
640 | } | |
641 | ||
642 | // Perform a union between 2 relations. *this ||= p. | |
643 | ||
644 | bool | |
645 | value_relation::union_ (value_relation &p) | |
646 | { | |
647 | // Save previous value | |
648 | relation_kind old = related; | |
649 | ||
650 | if (p.op1 () == op1 () && p.op2 () == op2 ()) | |
651 | related = relation_union (kind(), p.kind()); | |
652 | else if (p.op2 () == op1 () && p.op1 () == op2 ()) | |
653 | related = relation_union (kind(), relation_swap (p.kind ())); | |
654 | else | |
655 | return false; | |
656 | ||
657 | return old != related; | |
658 | } | |
659 | ||
675a3e40 AM |
660 | // Identify and apply any transitive relations between REL |
661 | // and THIS. Return true if there was a transformation. | |
662 | ||
663 | bool | |
664 | value_relation::apply_transitive (const value_relation &rel) | |
665 | { | |
666 | relation_kind k = VREL_NONE; | |
667 | ||
668 | // Idenity any common operand, and notrmalize the relations to | |
669 | // the form : A < B B < C produces A < C | |
670 | if (rel.op1 () == name2) | |
671 | { | |
672 | // A < B B < C | |
673 | if (rel.op2 () == name1) | |
674 | return false; | |
675 | k = relation_transitive (kind (), rel.kind ()); | |
676 | if (k != VREL_NONE) | |
677 | { | |
678 | related = k; | |
679 | name2 = rel.op2 (); | |
680 | return true; | |
681 | } | |
682 | } | |
683 | else if (rel.op1 () == name1) | |
684 | { | |
685 | // B > A B < C | |
686 | if (rel.op2 () == name2) | |
687 | return false; | |
688 | k = relation_transitive (relation_swap (kind ()), rel.kind ()); | |
689 | if (k != VREL_NONE) | |
690 | { | |
691 | related = k; | |
692 | name1 = name2; | |
693 | name2 = rel.op2 (); | |
694 | return true; | |
695 | } | |
696 | } | |
697 | else if (rel.op2 () == name2) | |
698 | { | |
699 | // A < B C > B | |
700 | if (rel.op1 () == name1) | |
701 | return false; | |
702 | k = relation_transitive (kind (), relation_swap (rel.kind ())); | |
703 | if (k != VREL_NONE) | |
704 | { | |
705 | related = k; | |
706 | name2 = rel.op1 (); | |
707 | return true; | |
708 | } | |
709 | } | |
710 | else if (rel.op2 () == name1) | |
711 | { | |
712 | // B > A C > B | |
713 | if (rel.op1 () == name2) | |
714 | return false; | |
715 | k = relation_transitive (relation_swap (kind ()), | |
716 | relation_swap (rel.kind ())); | |
717 | if (k != VREL_NONE) | |
718 | { | |
719 | related = k; | |
720 | name1 = name2; | |
721 | name2 = rel.op1 (); | |
722 | return true; | |
723 | } | |
724 | } | |
725 | return false; | |
726 | } | |
3aaa69e5 AM |
727 | |
728 | // Dump the relation to file F. | |
729 | ||
730 | void | |
731 | value_relation::dump (FILE *f) const | |
732 | { | |
733 | if (!name1 || !name2) | |
734 | { | |
735 | fprintf (f, "uninitialized"); | |
736 | return; | |
737 | } | |
738 | fputc ('(', f); | |
739 | print_generic_expr (f, op1 (), TDF_SLIM); | |
740 | print_relation (f, kind ()); | |
741 | print_generic_expr (f, op2 (), TDF_SLIM); | |
742 | fputc(')', f); | |
743 | } | |
744 | ||
745 | // This container is used to link relations in a chain. | |
746 | ||
747 | class relation_chain : public value_relation | |
748 | { | |
749 | public: | |
750 | relation_chain *m_next; | |
751 | }; | |
752 | ||
753 | // ------------------------------------------------------------------------ | |
754 | ||
3674d8e6 AM |
755 | // Find the relation between any ssa_name in B1 and any name in B2 in LIST. |
756 | // This will allow equivalencies to be applied to any SSA_NAME in a relation. | |
757 | ||
758 | relation_kind | |
759 | relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const | |
760 | { | |
761 | if (!m_names) | |
762 | return VREL_NONE; | |
763 | ||
764 | // If both b1 and b2 aren't referenced in thie block, cant be a relation | |
765 | if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2)) | |
766 | return VREL_NONE; | |
767 | ||
768 | // Search for the fiorst relation that contains BOTH an element from B1 | |
769 | // and B2, and return that relation. | |
770 | for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next) | |
771 | { | |
772 | unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); | |
773 | unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); | |
774 | if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2)) | |
775 | return ptr->kind (); | |
776 | if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1)) | |
777 | return relation_swap (ptr->kind ()); | |
778 | } | |
779 | ||
780 | return VREL_NONE; | |
781 | } | |
782 | ||
3aaa69e5 AM |
783 | // Instantiate a relation oracle. |
784 | ||
3674d8e6 | 785 | dom_oracle::dom_oracle () |
3aaa69e5 AM |
786 | { |
787 | m_relations.create (0); | |
788 | m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
789 | m_relation_set = BITMAP_ALLOC (&m_bitmaps); | |
790 | m_tmp = BITMAP_ALLOC (&m_bitmaps); | |
675a3e40 | 791 | m_tmp2 = BITMAP_ALLOC (&m_bitmaps); |
3aaa69e5 AM |
792 | } |
793 | ||
794 | // Destruct a relation oracle. | |
795 | ||
3674d8e6 | 796 | dom_oracle::~dom_oracle () |
3aaa69e5 AM |
797 | { |
798 | m_relations.release (); | |
799 | } | |
800 | ||
801 | // Register relation K between ssa_name OP1 and OP2 on STMT. | |
802 | ||
803 | void | |
3674d8e6 AM |
804 | relation_oracle::register_stmt (gimple *stmt, relation_kind k, tree op1, |
805 | tree op2) | |
3aaa69e5 AM |
806 | { |
807 | gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); | |
808 | gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); | |
809 | gcc_checking_assert (stmt && gimple_bb (stmt)); | |
810 | ||
811 | // Don't register lack of a relation. | |
812 | if (k == VREL_NONE) | |
813 | return; | |
814 | ||
815 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
816 | { | |
817 | value_relation vr (k, op1, op2); | |
818 | fprintf (dump_file, " Registering value_relation "); | |
819 | vr.dump (dump_file); | |
820 | fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index); | |
821 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
822 | } | |
823 | ||
5d110fe9 AM |
824 | // If an equivalence is being added between a PHI and one of its arguments |
825 | // make sure that that argument is not defined in the same block. | |
826 | // This can happen along back edges and the equivalence will not be | |
827 | // applicable as it would require a use before def. | |
828 | if (k == EQ_EXPR && is_a<gphi *> (stmt)) | |
829 | { | |
830 | tree phi_def = gimple_phi_result (stmt); | |
831 | gcc_checking_assert (phi_def == op1 || phi_def == op2); | |
832 | tree arg = op2; | |
833 | if (phi_def == op2) | |
834 | arg = op1; | |
835 | if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg))) | |
836 | { | |
837 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
838 | { | |
839 | fprintf (dump_file, " Not registered due to "); | |
840 | print_generic_expr (dump_file, arg, TDF_SLIM); | |
841 | fprintf (dump_file, " being defined in the same block.\n"); | |
842 | } | |
843 | return; | |
844 | } | |
845 | } | |
3674d8e6 | 846 | register_relation (gimple_bb (stmt), k, op1, op2); |
3aaa69e5 AM |
847 | } |
848 | ||
849 | // Register relation K between ssa_name OP1 and OP2 on edge E. | |
850 | ||
851 | void | |
3674d8e6 | 852 | relation_oracle::register_edge (edge e, relation_kind k, tree op1, tree op2) |
3aaa69e5 AM |
853 | { |
854 | gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); | |
855 | gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); | |
856 | ||
857 | // Do not register lack of relation, or blocks which have more than | |
858 | // edge E for a predecessor. | |
859 | if (k == VREL_NONE || !single_pred_p (e->dest)) | |
860 | return; | |
861 | ||
862 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
863 | { | |
864 | value_relation vr (k, op1, op2); | |
865 | fprintf (dump_file, " Registering value_relation "); | |
866 | vr.dump (dump_file); | |
867 | fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index); | |
868 | } | |
869 | ||
3674d8e6 AM |
870 | register_relation (e->dest, k, op1, op2); |
871 | } | |
872 | ||
873 | // Register relation K between OP! and OP2 in block BB. | |
874 | // This creates the record and searches for existing records in the dominator | |
875 | // tree to merge with. | |
876 | ||
877 | void | |
878 | dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1, | |
879 | tree op2) | |
0187c03b AM |
880 | { |
881 | // If the 2 ssa_names are the same, do nothing. An equivalence is implied, | |
882 | // and no other relation makes sense. | |
883 | if (op1 == op2) | |
884 | return; | |
885 | ||
886 | // Equivalencies are handled by the equivalence oracle. | |
3aaa69e5 | 887 | if (k == EQ_EXPR) |
3674d8e6 | 888 | equiv_oracle::register_relation (bb, k, op1, op2); |
3aaa69e5 | 889 | else |
3674d8e6 AM |
890 | { |
891 | relation_chain *ptr = set_one_relation (bb, k, op1, op2); | |
892 | register_transitives (bb, *ptr); | |
893 | } | |
3aaa69e5 AM |
894 | } |
895 | ||
896 | // Register relation K between OP! and OP2 in block BB. | |
897 | // This creates the record and searches for existing records in the dominator | |
898 | // tree to merge with. | |
899 | ||
3674d8e6 AM |
900 | relation_chain * |
901 | dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1, | |
902 | tree op2) | |
3aaa69e5 | 903 | { |
3674d8e6 | 904 | gcc_checking_assert (k != VREL_NONE && k != EQ_EXPR); |
3aaa69e5 AM |
905 | |
906 | value_relation vr(k, op1, op2); | |
907 | int bbi = bb->index; | |
908 | ||
909 | if (bbi >= (int)m_relations.length()) | |
910 | m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
911 | ||
912 | // Summary bitmap indicating what ssa_names have relations in this BB. | |
913 | bitmap bm = m_relations[bbi].m_names; | |
914 | if (!bm) | |
915 | bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps); | |
916 | unsigned v1 = SSA_NAME_VERSION (op1); | |
917 | unsigned v2 = SSA_NAME_VERSION (op2); | |
918 | ||
919 | relation_kind curr; | |
920 | relation_chain *ptr; | |
921 | curr = find_relation_block (bbi, v1, v2, &ptr); | |
922 | // There is an existing relation in this block, just intersect with it. | |
923 | if (curr != VREL_NONE) | |
924 | { | |
925 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
926 | { | |
927 | fprintf (dump_file, " Intersecting with existing "); | |
928 | ptr->dump (dump_file); | |
929 | } | |
930 | // Check into whether we can simply replace the relation rather than | |
931 | // intersecting it. THis may help with some optimistic iterative | |
932 | // updating algorithms. | |
933 | ptr->intersect (vr); | |
934 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
935 | { | |
936 | fprintf (dump_file, " to produce "); | |
937 | ptr->dump (dump_file); | |
938 | fprintf (dump_file, "\n"); | |
939 | } | |
675a3e40 AM |
940 | } |
941 | else | |
942 | { | |
943 | // Check for an existing relation further up the DOM chain. | |
944 | // By including dominating relations, The first one found in any search | |
945 | // will be the aggregate of all the previous ones. | |
946 | curr = find_relation_dom (bb, v1, v2); | |
947 | if (curr != VREL_NONE) | |
948 | k = relation_intersect (curr, k); | |
949 | ||
950 | bitmap_set_bit (bm, v1); | |
951 | bitmap_set_bit (bm, v2); | |
952 | bitmap_set_bit (m_relation_set, v1); | |
953 | bitmap_set_bit (m_relation_set, v2); | |
954 | ||
955 | ptr = (relation_chain *) obstack_alloc (&m_chain_obstack, | |
956 | sizeof (relation_chain)); | |
957 | ptr->set_relation (k, op1, op2); | |
958 | ptr->m_next = m_relations[bbi].m_head; | |
3674d8e6 | 959 | m_relations[bbi].m_head = ptr; |
3aaa69e5 | 960 | } |
3674d8e6 | 961 | return ptr; |
675a3e40 AM |
962 | } |
963 | ||
964 | // Starting at ROOT_BB search the DOM tree looking for relations which | |
965 | // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are | |
966 | // bitmaps for op1/op2 and any of their equivalences that should also be | |
967 | // considered. | |
968 | ||
969 | void | |
3674d8e6 AM |
970 | dom_oracle::register_transitives (basic_block root_bb, |
971 | const value_relation &relation) | |
675a3e40 AM |
972 | { |
973 | basic_block bb; | |
3674d8e6 AM |
974 | // Only apply transitives to certain kinds of operations. |
975 | switch (relation.kind ()) | |
976 | { | |
977 | case LE_EXPR: | |
978 | case LT_EXPR: | |
979 | case GT_EXPR: | |
980 | case GE_EXPR: | |
981 | break; | |
982 | default: | |
983 | return; | |
984 | } | |
985 | ||
986 | const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb); | |
987 | const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb); | |
988 | ||
675a3e40 AM |
989 | for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) |
990 | { | |
991 | int bbi = bb->index; | |
992 | if (bbi >= (int)m_relations.length()) | |
993 | continue; | |
994 | const_bitmap bm = m_relations[bbi].m_names; | |
995 | if (!bm) | |
996 | continue; | |
997 | if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2)) | |
998 | continue; | |
999 | // At least one of the 2 ops has a relation in this block. | |
1000 | relation_chain *ptr; | |
1001 | for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next) | |
1002 | { | |
1003 | // In the presence of an equivalence, 2 operands may do not | |
1004 | // naturally match. ie with equivalence a_2 == b_3 | |
1005 | // given c_1 < a_2 && b_3 < d_4 | |
1006 | // convert the second relation (b_3 < d_4) to match any | |
1007 | // equivalences to found in the first relation. | |
1008 | // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the | |
1009 | // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4 | |
1010 | ||
1011 | tree r1, r2; | |
1012 | tree p1 = ptr->op1 (); | |
1013 | tree p2 = ptr->op2 (); | |
1014 | // Find which equivalence is in the first operand. | |
1015 | if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1))) | |
1016 | r1 = p1; | |
1017 | else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2))) | |
1018 | r1 = p2; | |
1019 | else | |
1020 | r1 = NULL_TREE; | |
1021 | ||
1022 | // Find which equivalence is in the second operand. | |
1023 | if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1))) | |
1024 | r2 = p1; | |
1025 | else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2))) | |
1026 | r2 = p2; | |
1027 | else | |
1028 | r2 = NULL_TREE; | |
1029 | ||
1030 | // Ignore if both NULL (not relevant relation) or the same, | |
1031 | if (r1 == r2) | |
1032 | continue; | |
1033 | ||
1034 | // Any operand not an equivalence, just take the real operand. | |
1035 | if (!r1) | |
1036 | r1 = relation.op1 (); | |
1037 | if (!r2) | |
1038 | r2 = relation.op2 (); | |
1039 | ||
1040 | value_relation nr (relation.kind (), r1, r2); | |
1041 | if (nr.apply_transitive (*ptr)) | |
1042 | { | |
3674d8e6 | 1043 | set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ()); |
675a3e40 AM |
1044 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1045 | { | |
1046 | fprintf (dump_file, " Registering transitive relation "); | |
1047 | nr.dump (dump_file); | |
1048 | fputc ('\n', dump_file); | |
1049 | } | |
1050 | } | |
1051 | ||
1052 | } | |
1053 | } | |
1054 | } | |
1055 | ||
3aaa69e5 AM |
1056 | // Find the relation between any ssa_name in B1 and any name in B2 in block BB. |
1057 | // This will allow equivalencies to be applied to any SSA_NAME in a relation. | |
1058 | ||
1059 | relation_kind | |
3674d8e6 AM |
1060 | dom_oracle::find_relation_block (unsigned bb, const_bitmap b1, |
1061 | const_bitmap b2) const | |
3aaa69e5 | 1062 | { |
3aaa69e5 AM |
1063 | if (bb >= m_relations.length()) |
1064 | return VREL_NONE; | |
1065 | ||
3674d8e6 | 1066 | return m_relations[bb].find_relation (b1, b2); |
3aaa69e5 AM |
1067 | } |
1068 | ||
3674d8e6 AM |
1069 | // Search the DOM tree for a relation between an element of equivalency set B1 |
1070 | // and B2, starting with block BB. | |
3aaa69e5 AM |
1071 | |
1072 | relation_kind | |
3674d8e6 AM |
1073 | dom_oracle::query_relation (basic_block bb, const_bitmap b1, |
1074 | const_bitmap b2) | |
3aaa69e5 AM |
1075 | { |
1076 | relation_kind r; | |
3674d8e6 AM |
1077 | if (bitmap_equal_p (b1, b2)) |
1078 | return EQ_EXPR; | |
1079 | ||
3aaa69e5 AM |
1080 | // If either name does not occur in a relation anywhere, there isnt one. |
1081 | if (!bitmap_intersect_p (m_relation_set, b1) | |
1082 | || !bitmap_intersect_p (m_relation_set, b2)) | |
1083 | return VREL_NONE; | |
1084 | ||
1085 | // Search each block in the DOM tree checking. | |
1086 | for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
1087 | { | |
1088 | r = find_relation_block (bb->index, b1, b2); | |
1089 | if (r != VREL_NONE) | |
1090 | return r; | |
1091 | } | |
1092 | return VREL_NONE; | |
1093 | ||
1094 | } | |
1095 | ||
1096 | // Find a relation in block BB between ssa version V1 and V2. If a relation | |
1097 | // is found, return a pointer to the chain object in OBJ. | |
1098 | ||
1099 | relation_kind | |
3674d8e6 AM |
1100 | dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2, |
1101 | relation_chain **obj) const | |
3aaa69e5 AM |
1102 | { |
1103 | if (bb >= (int)m_relations.length()) | |
1104 | return VREL_NONE; | |
1105 | ||
1106 | const_bitmap bm = m_relations[bb].m_names; | |
1107 | if (!bm) | |
1108 | return VREL_NONE; | |
1109 | ||
1110 | // If both b1 and b2 aren't referenced in thie block, cant be a relation | |
1111 | if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2)) | |
1112 | return VREL_NONE; | |
1113 | ||
1114 | relation_chain *ptr; | |
1115 | for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next) | |
1116 | { | |
1117 | unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); | |
1118 | unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); | |
1119 | if (v1 == op1 && v2 == op2) | |
1120 | { | |
1121 | if (obj) | |
1122 | *obj = ptr; | |
1123 | return ptr->kind (); | |
1124 | } | |
1125 | if (v1 == op2 && v2 == op1) | |
1126 | { | |
1127 | if (obj) | |
1128 | *obj = ptr; | |
1129 | return relation_swap (ptr->kind ()); | |
1130 | } | |
1131 | } | |
1132 | ||
1133 | return VREL_NONE; | |
1134 | } | |
1135 | ||
1136 | // Find a relation between SSA version V1 and V2 in the dominator tree | |
1137 | // starting with block BB | |
1138 | ||
1139 | relation_kind | |
3674d8e6 | 1140 | dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const |
3aaa69e5 AM |
1141 | { |
1142 | relation_kind r; | |
1143 | // IF either name does not occur in a relation anywhere, there isnt one. | |
1144 | if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2)) | |
1145 | return VREL_NONE; | |
1146 | ||
1147 | for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
1148 | { | |
1149 | r = find_relation_block (bb->index, v1, v2); | |
1150 | if (r != VREL_NONE) | |
1151 | return r; | |
1152 | } | |
1153 | return VREL_NONE; | |
1154 | ||
1155 | } | |
1156 | ||
1157 | // Query if there is a relation between SSA1 and SS2 in block BB or a | |
1158 | // dominator of BB | |
1159 | ||
1160 | relation_kind | |
3674d8e6 | 1161 | dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) |
3aaa69e5 AM |
1162 | { |
1163 | relation_kind kind; | |
1164 | unsigned v1 = SSA_NAME_VERSION (ssa1); | |
1165 | unsigned v2 = SSA_NAME_VERSION (ssa2); | |
1166 | if (v1 == v2) | |
1167 | return EQ_EXPR; | |
1168 | ||
3674d8e6 | 1169 | // Check for equivalence first. They must be in each equivalency set. |
3aaa69e5 | 1170 | const_bitmap equiv1 = equiv_set (ssa1, bb); |
3674d8e6 AM |
1171 | const_bitmap equiv2 = equiv_set (ssa2, bb); |
1172 | if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1)) | |
3aaa69e5 AM |
1173 | return EQ_EXPR; |
1174 | ||
1175 | // Initially look for a direct relationship and just return that. | |
1176 | kind = find_relation_dom (bb, v1, v2); | |
1177 | if (kind != VREL_NONE) | |
1178 | return kind; | |
1179 | ||
3674d8e6 AM |
1180 | // Query using the equiovalence sets. |
1181 | kind = query_relation (bb, equiv1, equiv2); | |
3aaa69e5 AM |
1182 | return kind; |
1183 | } | |
1184 | ||
1185 | // Dump all the relations in block BB to file F. | |
1186 | ||
1187 | void | |
3674d8e6 | 1188 | dom_oracle::dump (FILE *f, basic_block bb) const |
3aaa69e5 AM |
1189 | { |
1190 | equiv_oracle::dump (f,bb); | |
1191 | ||
1192 | if (bb->index >= (int)m_relations.length ()) | |
1193 | return; | |
1194 | if (!m_relations[bb->index].m_names) | |
1195 | return; | |
1196 | ||
1197 | relation_chain *ptr = m_relations[bb->index].m_head; | |
1198 | for (; ptr; ptr = ptr->m_next) | |
1199 | { | |
1200 | fprintf (f, "Relational : "); | |
1201 | ptr->dump (f); | |
1202 | fprintf (f, "\n"); | |
1203 | } | |
1204 | } | |
1205 | ||
1206 | // Dump all the relations known to file F. | |
1207 | ||
1208 | void | |
3674d8e6 | 1209 | dom_oracle::dump (FILE *f) const |
3aaa69e5 AM |
1210 | { |
1211 | fprintf (f, "Relation dump\n"); | |
1212 | for (unsigned i = 0; i < m_relations.length (); i++) | |
ce0b409f AM |
1213 | if (BASIC_BLOCK_FOR_FN (cfun, i)) |
1214 | { | |
1215 | fprintf (f, "BB%d\n", i); | |
1216 | dump (f, BASIC_BLOCK_FOR_FN (cfun, i)); | |
1217 | } | |
3aaa69e5 | 1218 | } |
abcd2373 AH |
1219 | |
1220 | void | |
1221 | relation_oracle::debug () const | |
1222 | { | |
1223 | dump (stderr); | |
1224 | } | |
534c5352 AM |
1225 | |
1226 | path_oracle::path_oracle (relation_oracle *oracle) | |
1227 | { | |
1228 | m_root = oracle; | |
1229 | bitmap_obstack_initialize (&m_bitmaps); | |
1230 | obstack_init (&m_chain_obstack); | |
1231 | ||
1232 | // Initialize header records. | |
1233 | m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps); | |
1234 | m_equiv.m_bb = NULL; | |
1235 | m_equiv.m_next = NULL; | |
1236 | m_relations.m_names = BITMAP_ALLOC (&m_bitmaps); | |
1237 | m_relations.m_head = NULL; | |
4856699e | 1238 | m_killed_defs = BITMAP_ALLOC (&m_bitmaps); |
534c5352 AM |
1239 | } |
1240 | ||
1241 | path_oracle::~path_oracle () | |
1242 | { | |
1243 | obstack_free (&m_chain_obstack, NULL); | |
1244 | bitmap_obstack_release (&m_bitmaps); | |
1245 | } | |
1246 | ||
1247 | // Return the equiv set for SSA, and if there isn't one, check for equivs | |
1248 | // starting in block BB. | |
1249 | ||
1250 | const_bitmap | |
1251 | path_oracle::equiv_set (tree ssa, basic_block bb) | |
1252 | { | |
1253 | // Check the list first. | |
1254 | equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa)); | |
1255 | if (ptr) | |
1256 | return ptr->m_names; | |
1257 | ||
1258 | // Otherwise defer to the root oracle. | |
1259 | if (m_root) | |
1260 | return m_root->equiv_set (ssa, bb); | |
1261 | ||
1262 | // Allocate a throw away bitmap if there isn't a root oracle. | |
1263 | bitmap tmp = BITMAP_ALLOC (&m_bitmaps); | |
1264 | bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa)); | |
1265 | return tmp; | |
1266 | } | |
1267 | ||
1268 | // Register an equivalence between SSA1 and SSA2 resolving unkowns from | |
1269 | // block BB. | |
1270 | ||
1271 | void | |
1272 | path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2) | |
1273 | { | |
1274 | const_bitmap equiv_1 = equiv_set (ssa1, bb); | |
1275 | const_bitmap equiv_2 = equiv_set (ssa2, bb); | |
1276 | ||
1277 | // Check if they are the same set, if so, we're done. | |
1278 | if (bitmap_equal_p (equiv_1, equiv_2)) | |
1279 | return; | |
1280 | ||
1281 | // Don't mess around, simply create a new record and insert it first. | |
1282 | bitmap b = BITMAP_ALLOC (&m_bitmaps); | |
1283 | bitmap_copy (b, equiv_1); | |
1284 | bitmap_ior_into (b, equiv_2); | |
1285 | ||
1286 | equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, | |
1287 | sizeof (equiv_chain)); | |
1288 | ptr->m_names = b; | |
1289 | ptr->m_bb = NULL; | |
1290 | ptr->m_next = m_equiv.m_next; | |
1291 | m_equiv.m_next = ptr; | |
1292 | bitmap_ior_into (m_equiv.m_names, b); | |
1293 | } | |
1294 | ||
8a0fadda AH |
1295 | // Register killing definition of an SSA_NAME. |
1296 | ||
1297 | void | |
1298 | path_oracle::killing_def (tree ssa) | |
1299 | { | |
1300 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1301 | { | |
1302 | fprintf (dump_file, " Registering killing_def (path_oracle) "); | |
1303 | print_generic_expr (dump_file, ssa, TDF_SLIM); | |
1304 | fprintf (dump_file, "\n"); | |
1305 | } | |
1306 | ||
9f4edfc1 | 1307 | unsigned v = SSA_NAME_VERSION (ssa); |
9f4edfc1 | 1308 | |
4856699e AH |
1309 | bitmap_set_bit (m_killed_defs, v); |
1310 | ||
6ef9ad93 AH |
1311 | // Walk the equivalency list and remove SSA from any equivalencies. |
1312 | if (bitmap_bit_p (m_equiv.m_names, v)) | |
1313 | { | |
6ef9ad93 AH |
1314 | for (equiv_chain *ptr = m_equiv.m_next; ptr; ptr = ptr->m_next) |
1315 | if (bitmap_bit_p (ptr->m_names, v)) | |
1316 | bitmap_clear_bit (ptr->m_names, v); | |
1317 | } | |
dc173a43 AH |
1318 | else |
1319 | bitmap_set_bit (m_equiv.m_names, v); | |
1320 | ||
1321 | // Now add an equivalency with itself so we don't look to the root oracle. | |
1322 | bitmap b = BITMAP_ALLOC (&m_bitmaps); | |
1323 | bitmap_set_bit (b, v); | |
1324 | equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, | |
1325 | sizeof (equiv_chain)); | |
1326 | ptr->m_names = b; | |
1327 | ptr->m_bb = NULL; | |
1328 | ptr->m_next = m_equiv.m_next; | |
1329 | m_equiv.m_next = ptr; | |
6ef9ad93 AH |
1330 | |
1331 | // Walk the relation list and remove SSA from any relations. | |
9f4edfc1 AH |
1332 | if (!bitmap_bit_p (m_relations.m_names, v)) |
1333 | return; | |
1334 | ||
1335 | bitmap_clear_bit (m_relations.m_names, v); | |
1336 | relation_chain **prev = &(m_relations.m_head); | |
1337 | relation_chain *next = NULL; | |
1338 | for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next) | |
1339 | { | |
1340 | gcc_checking_assert (*prev == ptr); | |
1341 | next = ptr->m_next; | |
1342 | if (SSA_NAME_VERSION (ptr->op1 ()) == v | |
1343 | || SSA_NAME_VERSION (ptr->op2 ()) == v) | |
1344 | *prev = ptr->m_next; | |
1345 | else | |
1346 | prev = &(ptr->m_next); | |
1347 | } | |
8a0fadda AH |
1348 | } |
1349 | ||
534c5352 AM |
1350 | // Register relation K between SSA1 and SSA2, resolving unknowns by |
1351 | // querying from BB. | |
1352 | ||
1353 | void | |
1354 | path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1, | |
1355 | tree ssa2) | |
1356 | { | |
1357 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1358 | { | |
1359 | value_relation vr (k, ssa1, ssa2); | |
1360 | fprintf (dump_file, " Registering value_relation (path_oracle) "); | |
1361 | vr.dump (dump_file); | |
1362 | fprintf (dump_file, " (bb%d)\n", bb->index); | |
1363 | } | |
1364 | ||
1365 | if (k == EQ_EXPR) | |
1366 | { | |
1367 | register_equiv (bb, ssa1, ssa2); | |
1368 | return; | |
1369 | } | |
1370 | ||
1371 | relation_kind curr = query_relation (bb, ssa1, ssa2); | |
1372 | if (curr != VREL_NONE) | |
1373 | k = relation_intersect (curr, k); | |
1374 | ||
1375 | bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1)); | |
1376 | bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2)); | |
1377 | relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack, | |
1378 | sizeof (relation_chain)); | |
1379 | ptr->set_relation (k, ssa1, ssa2); | |
1380 | ptr->m_next = m_relations.m_head; | |
1381 | m_relations.m_head = ptr; | |
1382 | } | |
1383 | ||
1384 | // Query for a relationship between equiv set B1 and B2, resolving unknowns | |
1385 | // starting at block BB. | |
1386 | ||
1387 | relation_kind | |
1388 | path_oracle::query_relation (basic_block bb, const_bitmap b1, const_bitmap b2) | |
1389 | { | |
1390 | if (bitmap_equal_p (b1, b2)) | |
1391 | return EQ_EXPR; | |
1392 | ||
1393 | relation_kind k = m_relations.find_relation (b1, b2); | |
1394 | ||
4856699e AH |
1395 | // Do not look at the root oracle for names that have been killed |
1396 | // along the path. | |
1397 | if (bitmap_intersect_p (m_killed_defs, b1) | |
1398 | || bitmap_intersect_p (m_killed_defs, b2)) | |
1399 | return k; | |
1400 | ||
534c5352 AM |
1401 | if (k == VREL_NONE && m_root) |
1402 | k = m_root->query_relation (bb, b1, b2); | |
1403 | ||
1404 | return k; | |
1405 | } | |
1406 | ||
1407 | // Query for a relationship between SSA1 and SSA2, resolving unknowns | |
1408 | // starting at block BB. | |
1409 | ||
1410 | relation_kind | |
1411 | path_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) | |
1412 | { | |
1413 | unsigned v1 = SSA_NAME_VERSION (ssa1); | |
1414 | unsigned v2 = SSA_NAME_VERSION (ssa2); | |
1415 | ||
1416 | if (v1 == v2) | |
1417 | return EQ_EXPR; | |
1418 | ||
1419 | const_bitmap equiv_1 = equiv_set (ssa1, bb); | |
1420 | const_bitmap equiv_2 = equiv_set (ssa2, bb); | |
1421 | if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1)) | |
1422 | return EQ_EXPR; | |
1423 | ||
1424 | return query_relation (bb, equiv_1, equiv_2); | |
1425 | } | |
1426 | ||
1427 | // Reset any relations registered on this path. | |
1428 | ||
1429 | void | |
1430 | path_oracle::reset_path () | |
1431 | { | |
1432 | m_equiv.m_next = NULL; | |
1433 | bitmap_clear (m_equiv.m_names); | |
1434 | m_relations.m_head = NULL; | |
1435 | bitmap_clear (m_relations.m_names); | |
1436 | } | |
1437 | ||
1438 | // Dump relation in basic block... Do nothing here. | |
1439 | ||
1440 | void | |
1441 | path_oracle::dump (FILE *, basic_block) const | |
1442 | { | |
1443 | } | |
1444 | ||
1445 | // Dump the relations and equivalencies found in the path. | |
1446 | ||
1447 | void | |
1448 | path_oracle::dump (FILE *f) const | |
1449 | { | |
1450 | equiv_chain *ptr = m_equiv.m_next; | |
2fc9b4d7 AH |
1451 | relation_chain *ptr2 = m_relations.m_head; |
1452 | ||
1453 | if (ptr || ptr2) | |
1454 | fprintf (f, "\npath_oracle:\n"); | |
1455 | ||
534c5352 AM |
1456 | for (; ptr; ptr = ptr->m_next) |
1457 | ptr->dump (f); | |
1458 | ||
534c5352 AM |
1459 | for (; ptr2; ptr2 = ptr2->m_next) |
1460 | { | |
1461 | fprintf (f, "Relational : "); | |
1462 | ptr2->dump (f); | |
1463 | fprintf (f, "\n"); | |
1464 | } | |
1465 | } |