]>
Commit | Line | Data |
---|---|---|
3aaa69e5 | 1 | /* Header file for the value range relational processing. |
a945c346 | 2 | Copyright (C) 2020-2024 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 | ||
0cdb609f | 35 | static const char *const kind_string[VREL_LAST] = |
b5563410 AM |
36 | { "varying", "undefined", "<", "<=", ">", ">=", "==", "!=", "pe8", "pe16", |
37 | "pe32", "pe64" }; | |
3aaa69e5 AM |
38 | |
39 | // Print a relation_kind REL to file F. | |
40 | ||
41 | void | |
42 | print_relation (FILE *f, relation_kind rel) | |
43 | { | |
ade5531c | 44 | fprintf (f, " %s ", kind_string[rel]); |
3aaa69e5 AM |
45 | } |
46 | ||
47 | // This table is used to negate the operands. op1 REL op2 -> !(op1 REL op2). | |
0cdb609f | 48 | static const unsigned char rr_negate_table[VREL_LAST] = { |
ade5531c AM |
49 | VREL_VARYING, VREL_UNDEFINED, VREL_GE, VREL_GT, VREL_LE, VREL_LT, VREL_NE, |
50 | VREL_EQ }; | |
3aaa69e5 AM |
51 | |
52 | // Negate the relation, as in logical negation. | |
53 | ||
54 | relation_kind | |
55 | relation_negate (relation_kind r) | |
56 | { | |
0cdb609f | 57 | return relation_kind (rr_negate_table [r]); |
3aaa69e5 AM |
58 | } |
59 | ||
60 | // This table is used to swap the operands. op1 REL op2 -> op2 REL op1. | |
0cdb609f | 61 | static const unsigned char rr_swap_table[VREL_LAST] = { |
ade5531c AM |
62 | VREL_VARYING, VREL_UNDEFINED, VREL_GT, VREL_GE, VREL_LT, VREL_LE, VREL_EQ, |
63 | VREL_NE }; | |
3aaa69e5 AM |
64 | |
65 | // Return the relation as if the operands were swapped. | |
66 | ||
67 | relation_kind | |
68 | relation_swap (relation_kind r) | |
69 | { | |
0cdb609f | 70 | return relation_kind (rr_swap_table [r]); |
3aaa69e5 AM |
71 | } |
72 | ||
73 | // This table is used to perform an intersection between 2 relations. | |
74 | ||
0cdb609f | 75 | static const unsigned char rr_intersect_table[VREL_LAST][VREL_LAST] = { |
ade5531c AM |
76 | // VREL_VARYING |
77 | { VREL_VARYING, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ, | |
78 | VREL_NE }, | |
79 | // VREL_UNDEFINED | |
80 | { VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, | |
81 | VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED }, | |
82 | // VREL_LT | |
83 | { VREL_LT, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_UNDEFINED, VREL_UNDEFINED, | |
84 | VREL_UNDEFINED, VREL_LT }, | |
85 | // VREL_LE | |
86 | { VREL_LE, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_UNDEFINED, VREL_EQ, | |
87 | VREL_EQ, VREL_LT }, | |
88 | // VREL_GT | |
89 | { VREL_GT, VREL_UNDEFINED, VREL_UNDEFINED, VREL_UNDEFINED, VREL_GT, VREL_GT, | |
90 | VREL_UNDEFINED, VREL_GT }, | |
91 | // VREL_GE | |
92 | { VREL_GE, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_GT, VREL_GE, | |
93 | VREL_EQ, VREL_GT }, | |
94 | // VREL_EQ | |
95 | { VREL_EQ, VREL_UNDEFINED, VREL_UNDEFINED, VREL_EQ, VREL_UNDEFINED, VREL_EQ, | |
96 | VREL_EQ, VREL_UNDEFINED }, | |
97 | // VREL_NE | |
98 | { VREL_NE, VREL_UNDEFINED, VREL_LT, VREL_LT, VREL_GT, VREL_GT, | |
99 | VREL_UNDEFINED, VREL_NE } }; | |
3aaa69e5 AM |
100 | |
101 | ||
675a3e40 | 102 | // Intersect relation R1 with relation R2 and return the resulting relation. |
3aaa69e5 AM |
103 | |
104 | relation_kind | |
105 | relation_intersect (relation_kind r1, relation_kind r2) | |
106 | { | |
0cdb609f | 107 | return relation_kind (rr_intersect_table[r1][r2]); |
3aaa69e5 AM |
108 | } |
109 | ||
110 | ||
111 | // This table is used to perform a union between 2 relations. | |
112 | ||
0cdb609f | 113 | static const unsigned char rr_union_table[VREL_LAST][VREL_LAST] = { |
ade5531c AM |
114 | // VREL_VARYING |
115 | { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, | |
116 | VREL_VARYING, VREL_VARYING, VREL_VARYING }, | |
117 | // VREL_UNDEFINED | |
c81e68a9 | 118 | { VREL_VARYING, VREL_UNDEFINED, VREL_LT, VREL_LE, VREL_GT, VREL_GE, |
ade5531c AM |
119 | VREL_EQ, VREL_NE }, |
120 | // VREL_LT | |
121 | { VREL_VARYING, VREL_LT, VREL_LT, VREL_LE, VREL_NE, VREL_VARYING, VREL_LE, | |
122 | VREL_NE }, | |
123 | // VREL_LE | |
124 | { VREL_VARYING, VREL_LE, VREL_LE, VREL_LE, VREL_VARYING, VREL_VARYING, | |
125 | VREL_LE, VREL_VARYING }, | |
126 | // VREL_GT | |
127 | { VREL_VARYING, VREL_GT, VREL_NE, VREL_VARYING, VREL_GT, VREL_GE, VREL_GE, | |
128 | VREL_NE }, | |
129 | // VREL_GE | |
130 | { VREL_VARYING, VREL_GE, VREL_VARYING, VREL_VARYING, VREL_GE, VREL_GE, | |
131 | VREL_GE, VREL_VARYING }, | |
132 | // VREL_EQ | |
133 | { VREL_VARYING, VREL_EQ, VREL_LE, VREL_LE, VREL_GE, VREL_GE, VREL_EQ, | |
134 | VREL_VARYING }, | |
135 | // VREL_NE | |
136 | { VREL_VARYING, VREL_NE, VREL_NE, VREL_VARYING, VREL_NE, VREL_VARYING, | |
137 | VREL_VARYING, VREL_NE } }; | |
3aaa69e5 AM |
138 | |
139 | // Union relation R1 with relation R2 and return the result. | |
140 | ||
141 | relation_kind | |
142 | relation_union (relation_kind r1, relation_kind r2) | |
143 | { | |
0cdb609f | 144 | return relation_kind (rr_union_table[r1][r2]); |
3aaa69e5 AM |
145 | } |
146 | ||
147 | ||
675a3e40 AM |
148 | // This table is used to determine transitivity between 2 relations. |
149 | // (A relation0 B) and (B relation1 C) implies (A result C) | |
150 | ||
0cdb609f | 151 | static const unsigned char rr_transitive_table[VREL_LAST][VREL_LAST] = { |
ade5531c AM |
152 | // VREL_VARYING |
153 | { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, | |
154 | VREL_VARYING, VREL_VARYING, VREL_VARYING }, | |
155 | // VREL_UNDEFINED | |
156 | { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, | |
157 | VREL_VARYING, VREL_VARYING, VREL_VARYING }, | |
158 | // VREL_LT | |
159 | { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LT, VREL_VARYING, VREL_VARYING, | |
160 | VREL_LT, VREL_VARYING }, | |
161 | // VREL_LE | |
162 | { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_VARYING, VREL_VARYING, | |
163 | VREL_LE, VREL_VARYING }, | |
164 | // VREL_GT | |
165 | { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GT, | |
166 | VREL_GT, VREL_VARYING }, | |
167 | // VREL_GE | |
168 | { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_GT, VREL_GE, | |
169 | VREL_GE, VREL_VARYING }, | |
170 | // VREL_EQ | |
171 | { VREL_VARYING, VREL_VARYING, VREL_LT, VREL_LE, VREL_GT, VREL_GE, VREL_EQ, | |
172 | VREL_VARYING }, | |
173 | // VREL_NE | |
174 | { VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, VREL_VARYING, | |
175 | VREL_VARYING, VREL_VARYING, VREL_VARYING } }; | |
675a3e40 AM |
176 | |
177 | // Apply transitive operation between relation R1 and relation R2, and | |
178 | // return the resulting relation, if any. | |
179 | ||
180 | relation_kind | |
181 | relation_transitive (relation_kind r1, relation_kind r2) | |
182 | { | |
0cdb609f | 183 | return relation_kind (rr_transitive_table[r1][r2]); |
675a3e40 AM |
184 | } |
185 | ||
b0892b1f AM |
186 | // When one name is an equivalence of another, ensure the equivalence |
187 | // range is correct. Specifically for floating point, a +0 is also | |
188 | // equivalent to a -0 which may not be reflected. See PR 111694. | |
189 | ||
190 | void | |
191 | adjust_equivalence_range (vrange &range) | |
192 | { | |
193 | if (range.undefined_p () || !is_a<frange> (range)) | |
194 | return; | |
195 | ||
196 | frange fr = as_a<frange> (range); | |
197 | // If range includes 0 make sure both signs of zero are included. | |
198 | if (fr.contains_p (dconst0) || fr.contains_p (dconstm0)) | |
199 | { | |
200 | frange zeros (range.type (), dconstm0, dconst0); | |
201 | range.union_ (zeros); | |
202 | } | |
203 | } | |
204 | ||
1d2aa262 AM |
205 | // This vector maps a relation to the equivalent tree code. |
206 | ||
0cdb609f | 207 | static const tree_code relation_to_code [VREL_LAST] = { |
1d2aa262 AM |
208 | ERROR_MARK, ERROR_MARK, LT_EXPR, LE_EXPR, GT_EXPR, GE_EXPR, EQ_EXPR, |
209 | NE_EXPR }; | |
210 | ||
6b73c07e AM |
211 | // Given an equivalence set EQUIV, set all the bits in B that are still valid |
212 | // members of EQUIV in basic block BB. | |
213 | ||
214 | void | |
215 | relation_oracle::valid_equivs (bitmap b, const_bitmap equivs, basic_block bb) | |
216 | { | |
217 | unsigned i; | |
218 | bitmap_iterator bi; | |
219 | EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi) | |
220 | { | |
221 | tree ssa = ssa_name (i); | |
c9dbace0 AM |
222 | if (ssa && !SSA_NAME_IN_FREE_LIST (ssa)) |
223 | { | |
224 | const_bitmap ssa_equiv = equiv_set (ssa, bb); | |
225 | if (ssa_equiv == equivs) | |
226 | bitmap_set_bit (b, i); | |
227 | } | |
6b73c07e AM |
228 | } |
229 | } | |
230 | ||
67afcf28 AM |
231 | // Return any known relation between SSA1 and SSA2 before stmt S is executed. |
232 | // If GET_RANGE is true, query the range of both operands first to ensure | |
233 | // the definitions have been processed and any relations have be created. | |
234 | ||
235 | relation_kind | |
fca649de | 236 | relation_oracle::query (gimple *s, tree ssa1, tree ssa2) |
67afcf28 AM |
237 | { |
238 | if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME) | |
239 | return VREL_VARYING; | |
fca649de | 240 | return query (gimple_bb (s), ssa1, ssa2); |
67afcf28 AM |
241 | } |
242 | ||
243 | // Return any known relation between SSA1 and SSA2 on edge E. | |
244 | // If GET_RANGE is true, query the range of both operands first to ensure | |
245 | // the definitions have been processed and any relations have be created. | |
246 | ||
247 | relation_kind | |
fca649de | 248 | relation_oracle::query (edge e, tree ssa1, tree ssa2) |
67afcf28 AM |
249 | { |
250 | basic_block bb; | |
251 | if (TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME) | |
252 | return VREL_VARYING; | |
253 | ||
254 | // Use destination block if it has a single predecessor, and this picks | |
255 | // up any relation on the edge. | |
256 | // Otherwise choose the src edge and the result is the same as on-exit. | |
257 | if (!single_pred_p (e->dest)) | |
258 | bb = e->src; | |
259 | else | |
260 | bb = e->dest; | |
261 | ||
fca649de | 262 | return query (bb, ssa1, ssa2); |
67afcf28 | 263 | } |
3aaa69e5 AM |
264 | // ------------------------------------------------------------------------- |
265 | ||
3aaa69e5 AM |
266 | // The very first element in the m_equiv chain is actually just a summary |
267 | // element in which the m_names bitmap is used to indicate that an ssa_name | |
268 | // has an equivalence set in this block. | |
269 | // This allows for much faster traversal of the DOM chain, as a search for | |
270 | // SSA_NAME simply requires walking the DOM chain until a block is found | |
271 | // which has the bit for SSA_NAME set. Then scan for the equivalency set in | |
3674d8e6 | 272 | // that block. No previous lists need be searched. |
3aaa69e5 | 273 | |
3674d8e6 AM |
274 | // If SSA has an equivalence in this list, find and return it. |
275 | // Otherwise return NULL. | |
276 | ||
277 | equiv_chain * | |
278 | equiv_chain::find (unsigned ssa) | |
279 | { | |
280 | equiv_chain *ptr = NULL; | |
281 | // If there are equiv sets and SSA is in one in this list, find it. | |
282 | // Otherwise return NULL. | |
283 | if (bitmap_bit_p (m_names, ssa)) | |
284 | { | |
285 | for (ptr = m_next; ptr; ptr = ptr->m_next) | |
286 | if (bitmap_bit_p (ptr->m_names, ssa)) | |
287 | break; | |
288 | } | |
289 | return ptr; | |
290 | } | |
3aaa69e5 AM |
291 | |
292 | // Dump the names in this equivalence set. | |
293 | ||
294 | void | |
295 | equiv_chain::dump (FILE *f) const | |
296 | { | |
297 | bitmap_iterator bi; | |
298 | unsigned i; | |
299 | ||
b5563410 | 300 | if (!m_names || bitmap_empty_p (m_names)) |
3aaa69e5 AM |
301 | return; |
302 | fprintf (f, "Equivalence set : ["); | |
303 | unsigned c = 0; | |
304 | EXECUTE_IF_SET_IN_BITMAP (m_names, 0, i, bi) | |
305 | { | |
306 | if (ssa_name (i)) | |
307 | { | |
308 | if (c++) | |
309 | fprintf (f, ", "); | |
310 | print_generic_expr (f, ssa_name (i), TDF_SLIM); | |
311 | } | |
312 | } | |
313 | fprintf (f, "]\n"); | |
314 | } | |
315 | ||
316 | // Instantiate an equivalency oracle. | |
317 | ||
318 | equiv_oracle::equiv_oracle () | |
319 | { | |
320 | bitmap_obstack_initialize (&m_bitmaps); | |
321 | m_equiv.create (0); | |
322 | m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
323 | m_equiv_set = BITMAP_ALLOC (&m_bitmaps); | |
caf3fe78 | 324 | bitmap_tree_view (m_equiv_set); |
3aaa69e5 | 325 | obstack_init (&m_chain_obstack); |
3674d8e6 AM |
326 | m_self_equiv.create (0); |
327 | m_self_equiv.safe_grow_cleared (num_ssa_names + 1); | |
b5563410 AM |
328 | m_partial.create (0); |
329 | m_partial.safe_grow_cleared (num_ssa_names + 1); | |
3aaa69e5 AM |
330 | } |
331 | ||
332 | // Destruct an equivalency oracle. | |
333 | ||
334 | equiv_oracle::~equiv_oracle () | |
335 | { | |
b5563410 | 336 | m_partial.release (); |
3674d8e6 | 337 | m_self_equiv.release (); |
3aaa69e5 AM |
338 | obstack_free (&m_chain_obstack, NULL); |
339 | m_equiv.release (); | |
340 | bitmap_obstack_release (&m_bitmaps); | |
341 | } | |
342 | ||
b5563410 AM |
343 | // Add a partial equivalence R between OP1 and OP2. |
344 | ||
345 | void | |
346 | equiv_oracle::add_partial_equiv (relation_kind r, tree op1, tree op2) | |
347 | { | |
348 | int v1 = SSA_NAME_VERSION (op1); | |
349 | int v2 = SSA_NAME_VERSION (op2); | |
350 | int prec2 = TYPE_PRECISION (TREE_TYPE (op2)); | |
351 | int bits = pe_to_bits (r); | |
352 | gcc_checking_assert (bits && prec2 >= bits); | |
353 | ||
354 | if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ()) | |
355 | m_partial.safe_grow_cleared (num_ssa_names + 1); | |
356 | gcc_checking_assert (v1 < (int)m_partial.length () | |
357 | && v2 < (int)m_partial.length ()); | |
358 | ||
359 | pe_slice &pe1 = m_partial[v1]; | |
360 | pe_slice &pe2 = m_partial[v2]; | |
361 | ||
362 | if (pe1.members) | |
363 | { | |
364 | // If the definition pe1 already has an entry, either the stmt is | |
365 | // being re-evaluated, or the def was used before being registered. | |
366 | // In either case, if PE2 has an entry, we simply do nothing. | |
367 | if (pe2.members) | |
368 | return; | |
8be20f3b AM |
369 | // If there are no uses of op2, do not register. |
370 | if (has_zero_uses (op2)) | |
371 | return; | |
b5563410 AM |
372 | // PE1 is the LHS and already has members, so everything in the set |
373 | // should be a slice of PE2 rather than PE1. | |
374 | pe2.code = pe_min (r, pe1.code); | |
375 | pe2.ssa_base = op2; | |
376 | pe2.members = pe1.members; | |
377 | bitmap_iterator bi; | |
378 | unsigned x; | |
379 | EXECUTE_IF_SET_IN_BITMAP (pe1.members, 0, x, bi) | |
380 | { | |
381 | m_partial[x].ssa_base = op2; | |
0205fbb9 | 382 | m_partial[x].code = pe_min (m_partial[x].code, pe2.code); |
b5563410 AM |
383 | } |
384 | bitmap_set_bit (pe1.members, v2); | |
385 | return; | |
386 | } | |
387 | if (pe2.members) | |
388 | { | |
8be20f3b AM |
389 | // If there are no uses of op1, do not register. |
390 | if (has_zero_uses (op1)) | |
391 | return; | |
b5563410 AM |
392 | pe1.ssa_base = pe2.ssa_base; |
393 | // If pe2 is a 16 bit value, but only an 8 bit copy, we can't be any | |
394 | // more than an 8 bit equivalence here, so choose MIN value. | |
395 | pe1.code = pe_min (r, pe2.code); | |
396 | pe1.members = pe2.members; | |
397 | bitmap_set_bit (pe1.members, v1); | |
398 | } | |
399 | else | |
400 | { | |
8be20f3b AM |
401 | // If there are no uses of either operand, do not register. |
402 | if (has_zero_uses (op1) || has_zero_uses (op2)) | |
403 | return; | |
b5563410 AM |
404 | // Neither name has an entry, simply create op1 as slice of op2. |
405 | pe2.code = bits_to_pe (TYPE_PRECISION (TREE_TYPE (op2))); | |
406 | if (pe2.code == VREL_VARYING) | |
407 | return; | |
408 | pe2.ssa_base = op2; | |
409 | pe2.members = BITMAP_ALLOC (&m_bitmaps); | |
410 | bitmap_set_bit (pe2.members, v2); | |
411 | pe1.ssa_base = op2; | |
412 | pe1.code = r; | |
413 | pe1.members = pe2.members; | |
414 | bitmap_set_bit (pe1.members, v1); | |
415 | } | |
416 | } | |
417 | ||
418 | // Return the set of partial equivalences associated with NAME. The bitmap | |
419 | // will be NULL if there are none. | |
420 | ||
421 | const pe_slice * | |
422 | equiv_oracle::partial_equiv_set (tree name) | |
423 | { | |
424 | int v = SSA_NAME_VERSION (name); | |
425 | if (v >= (int)m_partial.length ()) | |
426 | return NULL; | |
427 | return &m_partial[v]; | |
428 | } | |
429 | ||
430 | // Query if there is a partial equivalence between SSA1 and SSA2. Return | |
431 | // VREL_VARYING if there is not one. If BASE is non-null, return the base | |
432 | // ssa-name this is a slice of. | |
433 | ||
434 | relation_kind | |
435 | equiv_oracle::partial_equiv (tree ssa1, tree ssa2, tree *base) const | |
436 | { | |
437 | int v1 = SSA_NAME_VERSION (ssa1); | |
438 | int v2 = SSA_NAME_VERSION (ssa2); | |
439 | ||
440 | if (v1 >= (int)m_partial.length () || v2 >= (int)m_partial.length ()) | |
441 | return VREL_VARYING; | |
442 | ||
443 | const pe_slice &pe1 = m_partial[v1]; | |
444 | const pe_slice &pe2 = m_partial[v2]; | |
445 | if (pe1.members && pe2.members == pe1.members) | |
446 | { | |
447 | if (base) | |
448 | *base = pe1.ssa_base; | |
449 | return pe_min (pe1.code, pe2.code); | |
450 | } | |
451 | return VREL_VARYING; | |
452 | } | |
453 | ||
454 | ||
3aaa69e5 AM |
455 | // Find and return the equivalency set for SSA along the dominators of BB. |
456 | // This is the external API. | |
457 | ||
458 | const_bitmap | |
3674d8e6 | 459 | equiv_oracle::equiv_set (tree ssa, basic_block bb) |
3aaa69e5 AM |
460 | { |
461 | // Search the dominator tree for an equivalency. | |
462 | equiv_chain *equiv = find_equiv_dom (ssa, bb); | |
463 | if (equiv) | |
464 | return equiv->m_names; | |
465 | ||
3674d8e6 AM |
466 | // Otherwise return a cached equiv set containing just this SSA. |
467 | unsigned v = SSA_NAME_VERSION (ssa); | |
468 | if (v >= m_self_equiv.length ()) | |
469 | m_self_equiv.safe_grow_cleared (num_ssa_names + 1); | |
470 | ||
471 | if (!m_self_equiv[v]) | |
472 | { | |
473 | m_self_equiv[v] = BITMAP_ALLOC (&m_bitmaps); | |
474 | bitmap_set_bit (m_self_equiv[v], v); | |
475 | } | |
476 | return m_self_equiv[v]; | |
3aaa69e5 AM |
477 | } |
478 | ||
b5563410 | 479 | // Query if there is a relation (equivalence) between 2 SSA_NAMEs. |
3674d8e6 AM |
480 | |
481 | relation_kind | |
fca649de | 482 | equiv_oracle::query (basic_block bb, tree ssa1, tree ssa2) |
3674d8e6 AM |
483 | { |
484 | // If the 2 ssa names share the same equiv set, they are equal. | |
485 | if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb)) | |
ade5531c | 486 | return VREL_EQ; |
b5563410 AM |
487 | |
488 | // Check if there is a partial equivalence. | |
489 | return partial_equiv (ssa1, ssa2); | |
3674d8e6 AM |
490 | } |
491 | ||
c46b5b0a | 492 | // Query if there is a relation (equivalence) between 2 SSA_NAMEs. |
3674d8e6 AM |
493 | |
494 | relation_kind | |
fca649de AM |
495 | equiv_oracle::query (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1, |
496 | const_bitmap e2) | |
3674d8e6 AM |
497 | { |
498 | // If the 2 ssa names share the same equiv set, they are equal. | |
499 | if (bitmap_equal_p (e1, e2)) | |
ade5531c AM |
500 | return VREL_EQ; |
501 | return VREL_VARYING; | |
3674d8e6 | 502 | } |
3aaa69e5 AM |
503 | |
504 | // If SSA has an equivalence in block BB, find and return it. | |
505 | // Otherwise return NULL. | |
506 | ||
507 | equiv_chain * | |
508 | equiv_oracle::find_equiv_block (unsigned ssa, int bb) const | |
509 | { | |
3674d8e6 | 510 | if (bb >= (int)m_equiv.length () || !m_equiv[bb]) |
3aaa69e5 AM |
511 | return NULL; |
512 | ||
3674d8e6 | 513 | return m_equiv[bb]->find (ssa); |
3aaa69e5 AM |
514 | } |
515 | ||
516 | // Starting at block BB, walk the dominator chain looking for the nearest | |
517 | // equivalence set containing NAME. | |
518 | ||
519 | equiv_chain * | |
520 | equiv_oracle::find_equiv_dom (tree name, basic_block bb) const | |
521 | { | |
522 | unsigned v = SSA_NAME_VERSION (name); | |
523 | // Short circuit looking for names which have no equivalences. | |
524 | // Saves time looking for something which does not exist. | |
525 | if (!bitmap_bit_p (m_equiv_set, v)) | |
526 | return NULL; | |
527 | ||
528 | // NAME has at least once equivalence set, check to see if it has one along | |
529 | // the dominator tree. | |
530 | for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
531 | { | |
532 | equiv_chain *ptr = find_equiv_block (v, bb->index); | |
533 | if (ptr) | |
534 | return ptr; | |
535 | } | |
536 | return NULL; | |
537 | } | |
538 | ||
c46b5b0a | 539 | // Register equivalence between ssa_name V and set EQUIV in block BB, |
3aaa69e5 AM |
540 | |
541 | bitmap | |
542 | equiv_oracle::register_equiv (basic_block bb, unsigned v, equiv_chain *equiv) | |
543 | { | |
544 | // V will have an equivalency now. | |
545 | bitmap_set_bit (m_equiv_set, v); | |
546 | ||
547 | // If that equiv chain is in this block, simply use it. | |
548 | if (equiv->m_bb == bb) | |
549 | { | |
550 | bitmap_set_bit (equiv->m_names, v); | |
551 | bitmap_set_bit (m_equiv[bb->index]->m_names, v); | |
552 | return NULL; | |
553 | } | |
554 | ||
555 | // Otherwise create an equivalence for this block which is a copy | |
556 | // of equiv, the add V to the set. | |
557 | bitmap b = BITMAP_ALLOC (&m_bitmaps); | |
6b73c07e | 558 | valid_equivs (b, equiv->m_names, bb); |
3aaa69e5 AM |
559 | bitmap_set_bit (b, v); |
560 | return b; | |
561 | } | |
562 | ||
563 | // Register equivalence between set equiv_1 and equiv_2 in block BB. | |
564 | // Return NULL if either name can be merged with the other. Otherwise | |
565 | // return a pointer to the combined bitmap of names. This allows the | |
566 | // caller to do any setup required for a new element. | |
567 | ||
568 | bitmap | |
569 | equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1, | |
570 | equiv_chain *equiv_2) | |
571 | { | |
6b73c07e | 572 | // If equiv_1 is already in BB, use it as the combined set. |
3aaa69e5 AM |
573 | if (equiv_1->m_bb == bb) |
574 | { | |
6b73c07e | 575 | valid_equivs (equiv_1->m_names, equiv_2->m_names, bb); |
3aaa69e5 AM |
576 | // Its hard to delete from a single linked list, so |
577 | // just clear the second one. | |
578 | if (equiv_2->m_bb == bb) | |
579 | bitmap_clear (equiv_2->m_names); | |
580 | else | |
6b73c07e AM |
581 | // Ensure the new names are in the summary for BB. |
582 | bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_1->m_names); | |
3aaa69e5 AM |
583 | return NULL; |
584 | } | |
585 | // If equiv_2 is in BB, use it for the combined set. | |
586 | if (equiv_2->m_bb == bb) | |
587 | { | |
6b73c07e AM |
588 | valid_equivs (equiv_2->m_names, equiv_1->m_names, bb); |
589 | // Ensure the new names are in the summary. | |
590 | bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_2->m_names); | |
3aaa69e5 AM |
591 | return NULL; |
592 | } | |
593 | ||
594 | // At this point, neither equivalence is from this block. | |
595 | bitmap b = BITMAP_ALLOC (&m_bitmaps); | |
6b73c07e AM |
596 | valid_equivs (b, equiv_1->m_names, bb); |
597 | valid_equivs (b, equiv_2->m_names, bb); | |
3aaa69e5 AM |
598 | return b; |
599 | } | |
600 | ||
5d110fe9 AM |
601 | // Create an equivalency set containing only SSA in its definition block. |
602 | // This is done the first time SSA is registered in an equivalency and blocks | |
603 | // any DOM searches past the definition. | |
604 | ||
605 | void | |
606 | equiv_oracle::register_initial_def (tree ssa) | |
607 | { | |
608 | if (SSA_NAME_IS_DEFAULT_DEF (ssa)) | |
609 | return; | |
610 | basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (ssa)); | |
01c095ab AM |
611 | |
612 | // If defining stmt is not in the IL, simply return. | |
613 | if (!bb) | |
614 | return; | |
615 | gcc_checking_assert (!find_equiv_dom (ssa, bb)); | |
5d110fe9 AM |
616 | |
617 | unsigned v = SSA_NAME_VERSION (ssa); | |
618 | bitmap_set_bit (m_equiv_set, v); | |
619 | bitmap equiv_set = BITMAP_ALLOC (&m_bitmaps); | |
620 | bitmap_set_bit (equiv_set, v); | |
621 | add_equiv_to_block (bb, equiv_set); | |
622 | } | |
3aaa69e5 AM |
623 | |
624 | // Register an equivalence between SSA1 and SSA2 in block BB. | |
625 | // The equivalence oracle maintains a vector of equivalencies indexed by basic | |
c46b5b0a | 626 | // block. When an equivalence between SSA1 and SSA2 is registered in block BB, |
3aaa69e5 AM |
627 | // a query is made as to what equivalences both names have already, and |
628 | // any preexisting equivalences are merged to create a single equivalence | |
629 | // containing all the ssa_names in this basic block. | |
630 | ||
631 | void | |
fca649de | 632 | equiv_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2) |
3aaa69e5 | 633 | { |
b5563410 AM |
634 | // Process partial equivalencies. |
635 | if (relation_partial_equiv_p (k)) | |
636 | { | |
637 | add_partial_equiv (k, ssa1, ssa2); | |
638 | return; | |
639 | } | |
3674d8e6 | 640 | // Only handle equality relations. |
ade5531c | 641 | if (k != VREL_EQ) |
3674d8e6 AM |
642 | return; |
643 | ||
3aaa69e5 AM |
644 | unsigned v1 = SSA_NAME_VERSION (ssa1); |
645 | unsigned v2 = SSA_NAME_VERSION (ssa2); | |
5d110fe9 AM |
646 | |
647 | // If this is the first time an ssa_name has an equivalency registered | |
648 | // create a self-equivalency record in the def block. | |
649 | if (!bitmap_bit_p (m_equiv_set, v1)) | |
650 | register_initial_def (ssa1); | |
651 | if (!bitmap_bit_p (m_equiv_set, v2)) | |
652 | register_initial_def (ssa2); | |
653 | ||
3aaa69e5 AM |
654 | equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb); |
655 | equiv_chain *equiv_2 = find_equiv_dom (ssa2, bb); | |
656 | ||
657 | // Check if they are the same set | |
658 | if (equiv_1 && equiv_1 == equiv_2) | |
659 | return; | |
660 | ||
661 | bitmap equiv_set; | |
662 | ||
663 | // Case where we have 2 SSA_NAMEs that are not in any set. | |
664 | if (!equiv_1 && !equiv_2) | |
665 | { | |
666 | bitmap_set_bit (m_equiv_set, v1); | |
667 | bitmap_set_bit (m_equiv_set, v2); | |
668 | ||
669 | equiv_set = BITMAP_ALLOC (&m_bitmaps); | |
670 | bitmap_set_bit (equiv_set, v1); | |
671 | bitmap_set_bit (equiv_set, v2); | |
672 | } | |
673 | else if (!equiv_1 && equiv_2) | |
674 | equiv_set = register_equiv (bb, v1, equiv_2); | |
675 | else if (equiv_1 && !equiv_2) | |
676 | equiv_set = register_equiv (bb, v2, equiv_1); | |
677 | else | |
678 | equiv_set = register_equiv (bb, equiv_1, equiv_2); | |
679 | ||
680 | // A non-null return is a bitmap that is to be added to the current | |
681 | // block as a new equivalence. | |
682 | if (!equiv_set) | |
683 | return; | |
684 | ||
5d110fe9 AM |
685 | add_equiv_to_block (bb, equiv_set); |
686 | } | |
687 | ||
688 | // Add an equivalency record in block BB containing bitmap EQUIV_SET. | |
c46b5b0a | 689 | // Note the internal caller is responsible for allocating EQUIV_SET properly. |
5d110fe9 AM |
690 | |
691 | void | |
692 | equiv_oracle::add_equiv_to_block (basic_block bb, bitmap equiv_set) | |
693 | { | |
3aaa69e5 AM |
694 | equiv_chain *ptr; |
695 | ||
696 | // Check if this is the first time a block has an equivalence added. | |
697 | // and create a header block. And set the summary for this block. | |
d2d5ef6e | 698 | limit_check (bb); |
3aaa69e5 AM |
699 | if (!m_equiv[bb->index]) |
700 | { | |
701 | ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, | |
702 | sizeof (equiv_chain)); | |
703 | ptr->m_names = BITMAP_ALLOC (&m_bitmaps); | |
704 | bitmap_copy (ptr->m_names, equiv_set); | |
705 | ptr->m_bb = bb; | |
706 | ptr->m_next = NULL; | |
707 | m_equiv[bb->index] = ptr; | |
708 | } | |
709 | ||
710 | // Now create the element for this equiv set and initialize it. | |
711 | ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, sizeof (equiv_chain)); | |
712 | ptr->m_names = equiv_set; | |
713 | ptr->m_bb = bb; | |
714 | gcc_checking_assert (bb->index < (int)m_equiv.length ()); | |
715 | ptr->m_next = m_equiv[bb->index]->m_next; | |
716 | m_equiv[bb->index]->m_next = ptr; | |
717 | bitmap_ior_into (m_equiv[bb->index]->m_names, equiv_set); | |
718 | } | |
719 | ||
720 | // Make sure the BB vector is big enough and grow it if needed. | |
721 | ||
722 | void | |
723 | equiv_oracle::limit_check (basic_block bb) | |
724 | { | |
725 | int i = (bb) ? bb->index : last_basic_block_for_fn (cfun); | |
726 | if (i >= (int)m_equiv.length ()) | |
727 | m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
728 | } | |
729 | ||
730 | // Dump the equivalence sets in BB to file F. | |
731 | ||
732 | void | |
733 | equiv_oracle::dump (FILE *f, basic_block bb) const | |
734 | { | |
735 | if (bb->index >= (int)m_equiv.length ()) | |
736 | return; | |
b5563410 AM |
737 | // Process equivalences. |
738 | if (m_equiv[bb->index]) | |
739 | { | |
740 | equiv_chain *ptr = m_equiv[bb->index]->m_next; | |
741 | for (; ptr; ptr = ptr->m_next) | |
742 | ptr->dump (f); | |
743 | } | |
744 | // Look for partial equivalences defined in this block.. | |
745 | for (unsigned i = 0; i < num_ssa_names; i++) | |
746 | { | |
747 | tree name = ssa_name (i); | |
748 | if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name)) | |
749 | continue; | |
750 | if (i >= m_partial.length ()) | |
751 | break; | |
752 | tree base = m_partial[i].ssa_base; | |
753 | if (base && name != base && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb) | |
754 | { | |
755 | relation_kind k = partial_equiv (name, base); | |
756 | if (k != VREL_VARYING) | |
757 | { | |
758 | value_relation vr (k, name, base); | |
759 | fprintf (f, "Partial equiv "); | |
760 | vr.dump (f); | |
761 | fputc ('\n',f); | |
762 | } | |
763 | } | |
764 | } | |
3aaa69e5 AM |
765 | } |
766 | ||
767 | // Dump all equivalence sets known to the oracle. | |
768 | ||
769 | void | |
770 | equiv_oracle::dump (FILE *f) const | |
771 | { | |
772 | fprintf (f, "Equivalency dump\n"); | |
773 | for (unsigned i = 0; i < m_equiv.length (); i++) | |
ce0b409f | 774 | if (m_equiv[i] && BASIC_BLOCK_FOR_FN (cfun, i)) |
3aaa69e5 AM |
775 | { |
776 | fprintf (f, "BB%d\n", i); | |
777 | dump (f, BASIC_BLOCK_FOR_FN (cfun, i)); | |
778 | } | |
779 | } | |
780 | ||
781 | ||
782 | // -------------------------------------------------------------------------- | |
3aaa69e5 AM |
783 | // Negate the current relation. |
784 | ||
785 | void | |
786 | value_relation::negate () | |
787 | { | |
788 | related = relation_negate (related); | |
789 | } | |
790 | ||
3aaa69e5 AM |
791 | // Perform an intersection between 2 relations. *this &&= p. |
792 | ||
793 | bool | |
794 | value_relation::intersect (value_relation &p) | |
795 | { | |
796 | // Save previous value | |
797 | relation_kind old = related; | |
798 | ||
799 | if (p.op1 () == op1 () && p.op2 () == op2 ()) | |
800 | related = relation_intersect (kind (), p.kind ()); | |
801 | else if (p.op2 () == op1 () && p.op1 () == op2 ()) | |
802 | related = relation_intersect (kind (), relation_swap (p.kind ())); | |
803 | else | |
804 | return false; | |
805 | ||
806 | return old != related; | |
807 | } | |
808 | ||
809 | // Perform a union between 2 relations. *this ||= p. | |
810 | ||
811 | bool | |
812 | value_relation::union_ (value_relation &p) | |
813 | { | |
814 | // Save previous value | |
815 | relation_kind old = related; | |
816 | ||
817 | if (p.op1 () == op1 () && p.op2 () == op2 ()) | |
818 | related = relation_union (kind(), p.kind()); | |
819 | else if (p.op2 () == op1 () && p.op1 () == op2 ()) | |
820 | related = relation_union (kind(), relation_swap (p.kind ())); | |
821 | else | |
822 | return false; | |
823 | ||
824 | return old != related; | |
825 | } | |
826 | ||
675a3e40 AM |
827 | // Identify and apply any transitive relations between REL |
828 | // and THIS. Return true if there was a transformation. | |
829 | ||
830 | bool | |
831 | value_relation::apply_transitive (const value_relation &rel) | |
832 | { | |
ade5531c | 833 | relation_kind k = VREL_VARYING; |
675a3e40 | 834 | |
c46b5b0a | 835 | // Identify any common operand, and normalize the relations to |
675a3e40 AM |
836 | // the form : A < B B < C produces A < C |
837 | if (rel.op1 () == name2) | |
838 | { | |
839 | // A < B B < C | |
840 | if (rel.op2 () == name1) | |
841 | return false; | |
842 | k = relation_transitive (kind (), rel.kind ()); | |
ade5531c | 843 | if (k != VREL_VARYING) |
675a3e40 AM |
844 | { |
845 | related = k; | |
846 | name2 = rel.op2 (); | |
847 | return true; | |
848 | } | |
849 | } | |
850 | else if (rel.op1 () == name1) | |
851 | { | |
852 | // B > A B < C | |
853 | if (rel.op2 () == name2) | |
854 | return false; | |
855 | k = relation_transitive (relation_swap (kind ()), rel.kind ()); | |
ade5531c | 856 | if (k != VREL_VARYING) |
675a3e40 AM |
857 | { |
858 | related = k; | |
859 | name1 = name2; | |
860 | name2 = rel.op2 (); | |
861 | return true; | |
862 | } | |
863 | } | |
864 | else if (rel.op2 () == name2) | |
865 | { | |
866 | // A < B C > B | |
867 | if (rel.op1 () == name1) | |
868 | return false; | |
869 | k = relation_transitive (kind (), relation_swap (rel.kind ())); | |
ade5531c | 870 | if (k != VREL_VARYING) |
675a3e40 AM |
871 | { |
872 | related = k; | |
873 | name2 = rel.op1 (); | |
874 | return true; | |
875 | } | |
876 | } | |
877 | else if (rel.op2 () == name1) | |
878 | { | |
879 | // B > A C > B | |
880 | if (rel.op1 () == name2) | |
881 | return false; | |
882 | k = relation_transitive (relation_swap (kind ()), | |
883 | relation_swap (rel.kind ())); | |
ade5531c | 884 | if (k != VREL_VARYING) |
675a3e40 AM |
885 | { |
886 | related = k; | |
887 | name1 = name2; | |
888 | name2 = rel.op1 (); | |
889 | return true; | |
890 | } | |
891 | } | |
892 | return false; | |
893 | } | |
3aaa69e5 | 894 | |
99fda5de AM |
895 | // Create a trio from this value relation given LHS, OP1 and OP2. |
896 | ||
897 | relation_trio | |
898 | value_relation::create_trio (tree lhs, tree op1, tree op2) | |
899 | { | |
900 | relation_kind lhs_1; | |
901 | if (lhs == name1 && op1 == name2) | |
902 | lhs_1 = related; | |
903 | else if (lhs == name2 && op1 == name1) | |
904 | lhs_1 = relation_swap (related); | |
905 | else | |
906 | lhs_1 = VREL_VARYING; | |
907 | ||
908 | relation_kind lhs_2; | |
909 | if (lhs == name1 && op2 == name2) | |
910 | lhs_2 = related; | |
911 | else if (lhs == name2 && op2 == name1) | |
912 | lhs_2 = relation_swap (related); | |
913 | else | |
914 | lhs_2 = VREL_VARYING; | |
915 | ||
916 | relation_kind op_op; | |
917 | if (op1 == name1 && op2 == name2) | |
918 | op_op = related; | |
919 | else if (op1 == name2 && op2 == name1) | |
920 | op_op = relation_swap (related); | |
921 | else if (op1 == op2) | |
922 | op_op = VREL_EQ; | |
923 | else | |
924 | op_op = VREL_VARYING; | |
925 | ||
926 | return relation_trio (lhs_1, lhs_2, op_op); | |
927 | } | |
928 | ||
3aaa69e5 AM |
929 | // Dump the relation to file F. |
930 | ||
931 | void | |
932 | value_relation::dump (FILE *f) const | |
933 | { | |
934 | if (!name1 || !name2) | |
935 | { | |
fca52951 | 936 | fprintf (f, "no relation registered"); |
3aaa69e5 AM |
937 | return; |
938 | } | |
939 | fputc ('(', f); | |
940 | print_generic_expr (f, op1 (), TDF_SLIM); | |
941 | print_relation (f, kind ()); | |
942 | print_generic_expr (f, op2 (), TDF_SLIM); | |
943 | fputc(')', f); | |
944 | } | |
945 | ||
946 | // This container is used to link relations in a chain. | |
947 | ||
948 | class relation_chain : public value_relation | |
949 | { | |
950 | public: | |
951 | relation_chain *m_next; | |
952 | }; | |
953 | ||
954 | // ------------------------------------------------------------------------ | |
955 | ||
3674d8e6 AM |
956 | // Find the relation between any ssa_name in B1 and any name in B2 in LIST. |
957 | // This will allow equivalencies to be applied to any SSA_NAME in a relation. | |
958 | ||
959 | relation_kind | |
960 | relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const | |
961 | { | |
962 | if (!m_names) | |
ade5531c | 963 | return VREL_VARYING; |
3674d8e6 | 964 | |
c46b5b0a | 965 | // If both b1 and b2 aren't referenced in this block, cant be a relation |
3674d8e6 | 966 | if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2)) |
ade5531c | 967 | return VREL_VARYING; |
3674d8e6 | 968 | |
c46b5b0a | 969 | // Search for the first relation that contains BOTH an element from B1 |
3674d8e6 AM |
970 | // and B2, and return that relation. |
971 | for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next) | |
972 | { | |
973 | unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); | |
974 | unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); | |
975 | if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2)) | |
976 | return ptr->kind (); | |
977 | if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1)) | |
978 | return relation_swap (ptr->kind ()); | |
979 | } | |
980 | ||
ade5531c | 981 | return VREL_VARYING; |
3674d8e6 AM |
982 | } |
983 | ||
3aaa69e5 AM |
984 | // Instantiate a relation oracle. |
985 | ||
4c8b0858 | 986 | dom_oracle::dom_oracle (bool do_trans_p) |
3aaa69e5 | 987 | { |
4c8b0858 | 988 | m_do_trans_p = do_trans_p; |
3aaa69e5 AM |
989 | m_relations.create (0); |
990 | m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
991 | m_relation_set = BITMAP_ALLOC (&m_bitmaps); | |
992 | m_tmp = BITMAP_ALLOC (&m_bitmaps); | |
675a3e40 | 993 | m_tmp2 = BITMAP_ALLOC (&m_bitmaps); |
3aaa69e5 AM |
994 | } |
995 | ||
996 | // Destruct a relation oracle. | |
997 | ||
3674d8e6 | 998 | dom_oracle::~dom_oracle () |
3aaa69e5 AM |
999 | { |
1000 | m_relations.release (); | |
1001 | } | |
1002 | ||
1003 | // Register relation K between ssa_name OP1 and OP2 on STMT. | |
1004 | ||
1005 | void | |
fca649de | 1006 | relation_oracle::record (gimple *stmt, relation_kind k, tree op1, tree op2) |
3aaa69e5 AM |
1007 | { |
1008 | gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); | |
1009 | gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); | |
1010 | gcc_checking_assert (stmt && gimple_bb (stmt)); | |
1011 | ||
1012 | // Don't register lack of a relation. | |
ade5531c | 1013 | if (k == VREL_VARYING) |
3aaa69e5 AM |
1014 | return; |
1015 | ||
1016 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1017 | { | |
1018 | value_relation vr (k, op1, op2); | |
1019 | fprintf (dump_file, " Registering value_relation "); | |
1020 | vr.dump (dump_file); | |
1021 | fprintf (dump_file, " (bb%d) at ", gimple_bb (stmt)->index); | |
1022 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
1023 | } | |
1024 | ||
5d110fe9 AM |
1025 | // If an equivalence is being added between a PHI and one of its arguments |
1026 | // make sure that that argument is not defined in the same block. | |
1027 | // This can happen along back edges and the equivalence will not be | |
1028 | // applicable as it would require a use before def. | |
ade5531c | 1029 | if (k == VREL_EQ && is_a<gphi *> (stmt)) |
5d110fe9 AM |
1030 | { |
1031 | tree phi_def = gimple_phi_result (stmt); | |
1032 | gcc_checking_assert (phi_def == op1 || phi_def == op2); | |
1033 | tree arg = op2; | |
1034 | if (phi_def == op2) | |
1035 | arg = op1; | |
1036 | if (gimple_bb (stmt) == gimple_bb (SSA_NAME_DEF_STMT (arg))) | |
1037 | { | |
1038 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1039 | { | |
1040 | fprintf (dump_file, " Not registered due to "); | |
1041 | print_generic_expr (dump_file, arg, TDF_SLIM); | |
1042 | fprintf (dump_file, " being defined in the same block.\n"); | |
1043 | } | |
1044 | return; | |
1045 | } | |
1046 | } | |
fca649de | 1047 | record (gimple_bb (stmt), k, op1, op2); |
3aaa69e5 AM |
1048 | } |
1049 | ||
1050 | // Register relation K between ssa_name OP1 and OP2 on edge E. | |
1051 | ||
1052 | void | |
fca649de | 1053 | relation_oracle::record (edge e, relation_kind k, tree op1, tree op2) |
3aaa69e5 AM |
1054 | { |
1055 | gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); | |
1056 | gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); | |
1057 | ||
1058 | // Do not register lack of relation, or blocks which have more than | |
1059 | // edge E for a predecessor. | |
ade5531c | 1060 | if (k == VREL_VARYING || !single_pred_p (e->dest)) |
3aaa69e5 AM |
1061 | return; |
1062 | ||
1063 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1064 | { | |
1065 | value_relation vr (k, op1, op2); | |
1066 | fprintf (dump_file, " Registering value_relation "); | |
1067 | vr.dump (dump_file); | |
1068 | fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index); | |
1069 | } | |
1070 | ||
fca649de | 1071 | record (e->dest, k, op1, op2); |
3674d8e6 AM |
1072 | } |
1073 | ||
1074 | // Register relation K between OP! and OP2 in block BB. | |
1075 | // This creates the record and searches for existing records in the dominator | |
1076 | // tree to merge with. | |
1077 | ||
1078 | void | |
fca649de | 1079 | dom_oracle::record (basic_block bb, relation_kind k, tree op1, tree op2) |
0187c03b AM |
1080 | { |
1081 | // If the 2 ssa_names are the same, do nothing. An equivalence is implied, | |
1082 | // and no other relation makes sense. | |
1083 | if (op1 == op2) | |
1084 | return; | |
1085 | ||
1086 | // Equivalencies are handled by the equivalence oracle. | |
b5563410 | 1087 | if (relation_equiv_p (k)) |
fca649de | 1088 | equiv_oracle::record (bb, k, op1, op2); |
3aaa69e5 | 1089 | else |
3674d8e6 | 1090 | { |
5e47c933 AM |
1091 | // if neither op1 nor op2 are in a relation before this is registered, |
1092 | // there will be no transitive. | |
1093 | bool check = bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op1)) | |
1094 | || bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op2)); | |
3674d8e6 | 1095 | relation_chain *ptr = set_one_relation (bb, k, op1, op2); |
5e47c933 | 1096 | if (ptr && check) |
254ada46 | 1097 | register_transitives (bb, *ptr); |
3674d8e6 | 1098 | } |
3aaa69e5 AM |
1099 | } |
1100 | ||
1101 | // Register relation K between OP! and OP2 in block BB. | |
1102 | // This creates the record and searches for existing records in the dominator | |
254ada46 | 1103 | // tree to merge with. Return the record, or NULL if no record was created. |
3aaa69e5 | 1104 | |
3674d8e6 AM |
1105 | relation_chain * |
1106 | dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1, | |
1107 | tree op2) | |
3aaa69e5 | 1108 | { |
ade5531c | 1109 | gcc_checking_assert (k != VREL_VARYING && k != VREL_EQ); |
3aaa69e5 AM |
1110 | |
1111 | value_relation vr(k, op1, op2); | |
1112 | int bbi = bb->index; | |
1113 | ||
1114 | if (bbi >= (int)m_relations.length()) | |
1115 | m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); | |
1116 | ||
1117 | // Summary bitmap indicating what ssa_names have relations in this BB. | |
1118 | bitmap bm = m_relations[bbi].m_names; | |
1119 | if (!bm) | |
1120 | bm = m_relations[bbi].m_names = BITMAP_ALLOC (&m_bitmaps); | |
1121 | unsigned v1 = SSA_NAME_VERSION (op1); | |
1122 | unsigned v2 = SSA_NAME_VERSION (op2); | |
1123 | ||
1124 | relation_kind curr; | |
1125 | relation_chain *ptr; | |
1126 | curr = find_relation_block (bbi, v1, v2, &ptr); | |
1127 | // There is an existing relation in this block, just intersect with it. | |
ade5531c | 1128 | if (curr != VREL_VARYING) |
3aaa69e5 AM |
1129 | { |
1130 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1131 | { | |
1132 | fprintf (dump_file, " Intersecting with existing "); | |
1133 | ptr->dump (dump_file); | |
1134 | } | |
1135 | // Check into whether we can simply replace the relation rather than | |
e66236c6 | 1136 | // intersecting it. This may help with some optimistic iterative |
3aaa69e5 | 1137 | // updating algorithms. |
5e47c933 | 1138 | bool new_rel = ptr->intersect (vr); |
3aaa69e5 AM |
1139 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1140 | { | |
1141 | fprintf (dump_file, " to produce "); | |
1142 | ptr->dump (dump_file); | |
5e47c933 | 1143 | fprintf (dump_file, " %s.\n", new_rel ? "Updated" : "No Change"); |
3aaa69e5 | 1144 | } |
5e47c933 AM |
1145 | // If there was no change, return no record.. |
1146 | if (!new_rel) | |
1147 | return NULL; | |
675a3e40 AM |
1148 | } |
1149 | else | |
1150 | { | |
254ada46 AM |
1151 | if (m_relations[bbi].m_num_relations >= param_relation_block_limit) |
1152 | { | |
1153 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1154 | fprintf (dump_file, " Not registered due to bb being full\n"); | |
1155 | return NULL; | |
1156 | } | |
1157 | m_relations[bbi].m_num_relations++; | |
675a3e40 AM |
1158 | // Check for an existing relation further up the DOM chain. |
1159 | // By including dominating relations, The first one found in any search | |
1160 | // will be the aggregate of all the previous ones. | |
1161 | curr = find_relation_dom (bb, v1, v2); | |
ade5531c | 1162 | if (curr != VREL_VARYING) |
675a3e40 AM |
1163 | k = relation_intersect (curr, k); |
1164 | ||
1165 | bitmap_set_bit (bm, v1); | |
1166 | bitmap_set_bit (bm, v2); | |
1167 | bitmap_set_bit (m_relation_set, v1); | |
1168 | bitmap_set_bit (m_relation_set, v2); | |
1169 | ||
1170 | ptr = (relation_chain *) obstack_alloc (&m_chain_obstack, | |
1171 | sizeof (relation_chain)); | |
1172 | ptr->set_relation (k, op1, op2); | |
1173 | ptr->m_next = m_relations[bbi].m_head; | |
3674d8e6 | 1174 | m_relations[bbi].m_head = ptr; |
3aaa69e5 | 1175 | } |
3674d8e6 | 1176 | return ptr; |
675a3e40 AM |
1177 | } |
1178 | ||
1179 | // Starting at ROOT_BB search the DOM tree looking for relations which | |
1180 | // may produce transitive relations to RELATION. EQUIV1 and EQUIV2 are | |
1181 | // bitmaps for op1/op2 and any of their equivalences that should also be | |
1182 | // considered. | |
1183 | ||
1184 | void | |
3674d8e6 AM |
1185 | dom_oracle::register_transitives (basic_block root_bb, |
1186 | const value_relation &relation) | |
675a3e40 | 1187 | { |
4c8b0858 AM |
1188 | // Only register transitives if they are requested. |
1189 | if (!m_do_trans_p) | |
1190 | return; | |
675a3e40 | 1191 | basic_block bb; |
3674d8e6 AM |
1192 | // Only apply transitives to certain kinds of operations. |
1193 | switch (relation.kind ()) | |
1194 | { | |
ade5531c AM |
1195 | case VREL_LE: |
1196 | case VREL_LT: | |
1197 | case VREL_GT: | |
1198 | case VREL_GE: | |
3674d8e6 AM |
1199 | break; |
1200 | default: | |
1201 | return; | |
1202 | } | |
1203 | ||
1204 | const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb); | |
1205 | const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb); | |
1206 | ||
675a3e40 AM |
1207 | for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) |
1208 | { | |
1209 | int bbi = bb->index; | |
1210 | if (bbi >= (int)m_relations.length()) | |
1211 | continue; | |
1212 | const_bitmap bm = m_relations[bbi].m_names; | |
1213 | if (!bm) | |
1214 | continue; | |
1215 | if (!bitmap_intersect_p (bm, equiv1) && !bitmap_intersect_p (bm, equiv2)) | |
1216 | continue; | |
1217 | // At least one of the 2 ops has a relation in this block. | |
1218 | relation_chain *ptr; | |
1219 | for (ptr = m_relations[bbi].m_head; ptr ; ptr = ptr->m_next) | |
1220 | { | |
1221 | // In the presence of an equivalence, 2 operands may do not | |
1222 | // naturally match. ie with equivalence a_2 == b_3 | |
1223 | // given c_1 < a_2 && b_3 < d_4 | |
1224 | // convert the second relation (b_3 < d_4) to match any | |
1225 | // equivalences to found in the first relation. | |
1226 | // ie convert b_3 < d_4 to a_2 < d_4, which then exposes the | |
1227 | // transitive operation: c_1 < a_2 && a_2 < d_4 -> c_1 < d_4 | |
1228 | ||
1229 | tree r1, r2; | |
1230 | tree p1 = ptr->op1 (); | |
1231 | tree p2 = ptr->op2 (); | |
1232 | // Find which equivalence is in the first operand. | |
1233 | if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p1))) | |
1234 | r1 = p1; | |
1235 | else if (bitmap_bit_p (equiv1, SSA_NAME_VERSION (p2))) | |
1236 | r1 = p2; | |
1237 | else | |
1238 | r1 = NULL_TREE; | |
1239 | ||
1240 | // Find which equivalence is in the second operand. | |
1241 | if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p1))) | |
1242 | r2 = p1; | |
1243 | else if (bitmap_bit_p (equiv2, SSA_NAME_VERSION (p2))) | |
1244 | r2 = p2; | |
1245 | else | |
1246 | r2 = NULL_TREE; | |
1247 | ||
1248 | // Ignore if both NULL (not relevant relation) or the same, | |
1249 | if (r1 == r2) | |
1250 | continue; | |
1251 | ||
1252 | // Any operand not an equivalence, just take the real operand. | |
1253 | if (!r1) | |
1254 | r1 = relation.op1 (); | |
1255 | if (!r2) | |
1256 | r2 = relation.op2 (); | |
1257 | ||
1258 | value_relation nr (relation.kind (), r1, r2); | |
1259 | if (nr.apply_transitive (*ptr)) | |
1260 | { | |
254ada46 AM |
1261 | if (!set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ())) |
1262 | return; | |
675a3e40 AM |
1263 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1264 | { | |
1265 | fprintf (dump_file, " Registering transitive relation "); | |
1266 | nr.dump (dump_file); | |
1267 | fputc ('\n', dump_file); | |
1268 | } | |
1269 | } | |
1270 | ||
1271 | } | |
1272 | } | |
1273 | } | |
1274 | ||
3aaa69e5 AM |
1275 | // Find the relation between any ssa_name in B1 and any name in B2 in block BB. |
1276 | // This will allow equivalencies to be applied to any SSA_NAME in a relation. | |
1277 | ||
1278 | relation_kind | |
3674d8e6 AM |
1279 | dom_oracle::find_relation_block (unsigned bb, const_bitmap b1, |
1280 | const_bitmap b2) const | |
3aaa69e5 | 1281 | { |
3aaa69e5 | 1282 | if (bb >= m_relations.length()) |
ade5531c | 1283 | return VREL_VARYING; |
3aaa69e5 | 1284 | |
3674d8e6 | 1285 | return m_relations[bb].find_relation (b1, b2); |
3aaa69e5 AM |
1286 | } |
1287 | ||
3674d8e6 AM |
1288 | // Search the DOM tree for a relation between an element of equivalency set B1 |
1289 | // and B2, starting with block BB. | |
3aaa69e5 AM |
1290 | |
1291 | relation_kind | |
fca649de | 1292 | dom_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2) |
3aaa69e5 AM |
1293 | { |
1294 | relation_kind r; | |
3674d8e6 | 1295 | if (bitmap_equal_p (b1, b2)) |
ade5531c | 1296 | return VREL_EQ; |
3674d8e6 | 1297 | |
c46b5b0a | 1298 | // If either name does not occur in a relation anywhere, there isn't one. |
3aaa69e5 AM |
1299 | if (!bitmap_intersect_p (m_relation_set, b1) |
1300 | || !bitmap_intersect_p (m_relation_set, b2)) | |
ade5531c | 1301 | return VREL_VARYING; |
3aaa69e5 AM |
1302 | |
1303 | // Search each block in the DOM tree checking. | |
1304 | for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
1305 | { | |
1306 | r = find_relation_block (bb->index, b1, b2); | |
ade5531c | 1307 | if (r != VREL_VARYING) |
3aaa69e5 AM |
1308 | return r; |
1309 | } | |
ade5531c | 1310 | return VREL_VARYING; |
3aaa69e5 AM |
1311 | |
1312 | } | |
1313 | ||
1314 | // Find a relation in block BB between ssa version V1 and V2. If a relation | |
1315 | // is found, return a pointer to the chain object in OBJ. | |
1316 | ||
1317 | relation_kind | |
3674d8e6 AM |
1318 | dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2, |
1319 | relation_chain **obj) const | |
3aaa69e5 AM |
1320 | { |
1321 | if (bb >= (int)m_relations.length()) | |
ade5531c | 1322 | return VREL_VARYING; |
3aaa69e5 AM |
1323 | |
1324 | const_bitmap bm = m_relations[bb].m_names; | |
1325 | if (!bm) | |
ade5531c | 1326 | return VREL_VARYING; |
3aaa69e5 | 1327 | |
c46b5b0a | 1328 | // If both b1 and b2 aren't referenced in this block, cant be a relation |
3aaa69e5 | 1329 | if (!bitmap_bit_p (bm, v1) || !bitmap_bit_p (bm, v2)) |
ade5531c | 1330 | return VREL_VARYING; |
3aaa69e5 AM |
1331 | |
1332 | relation_chain *ptr; | |
1333 | for (ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next) | |
1334 | { | |
1335 | unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); | |
1336 | unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); | |
1337 | if (v1 == op1 && v2 == op2) | |
1338 | { | |
1339 | if (obj) | |
1340 | *obj = ptr; | |
1341 | return ptr->kind (); | |
1342 | } | |
1343 | if (v1 == op2 && v2 == op1) | |
1344 | { | |
1345 | if (obj) | |
1346 | *obj = ptr; | |
1347 | return relation_swap (ptr->kind ()); | |
1348 | } | |
1349 | } | |
1350 | ||
ade5531c | 1351 | return VREL_VARYING; |
3aaa69e5 AM |
1352 | } |
1353 | ||
1354 | // Find a relation between SSA version V1 and V2 in the dominator tree | |
1355 | // starting with block BB | |
1356 | ||
1357 | relation_kind | |
3674d8e6 | 1358 | dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const |
3aaa69e5 AM |
1359 | { |
1360 | relation_kind r; | |
c46b5b0a | 1361 | // IF either name does not occur in a relation anywhere, there isn't one. |
3aaa69e5 | 1362 | if (!bitmap_bit_p (m_relation_set, v1) || !bitmap_bit_p (m_relation_set, v2)) |
ade5531c | 1363 | return VREL_VARYING; |
3aaa69e5 AM |
1364 | |
1365 | for ( ; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
1366 | { | |
1367 | r = find_relation_block (bb->index, v1, v2); | |
ade5531c | 1368 | if (r != VREL_VARYING) |
3aaa69e5 AM |
1369 | return r; |
1370 | } | |
ade5531c | 1371 | return VREL_VARYING; |
3aaa69e5 AM |
1372 | |
1373 | } | |
1374 | ||
1375 | // Query if there is a relation between SSA1 and SS2 in block BB or a | |
1376 | // dominator of BB | |
1377 | ||
1378 | relation_kind | |
fca649de | 1379 | dom_oracle::query (basic_block bb, tree ssa1, tree ssa2) |
3aaa69e5 AM |
1380 | { |
1381 | relation_kind kind; | |
1382 | unsigned v1 = SSA_NAME_VERSION (ssa1); | |
1383 | unsigned v2 = SSA_NAME_VERSION (ssa2); | |
1384 | if (v1 == v2) | |
ade5531c | 1385 | return VREL_EQ; |
3aaa69e5 | 1386 | |
bf50499a AM |
1387 | // If v1 or v2 do not have any relations or equivalences, a partial |
1388 | // equivalence is the only possibility. | |
1389 | if ((!bitmap_bit_p (m_relation_set, v1) && !has_equiv_p (v1)) | |
1390 | || (!bitmap_bit_p (m_relation_set, v2) && !has_equiv_p (v2))) | |
1391 | return partial_equiv (ssa1, ssa2); | |
1392 | ||
3674d8e6 | 1393 | // Check for equivalence first. They must be in each equivalency set. |
3aaa69e5 | 1394 | const_bitmap equiv1 = equiv_set (ssa1, bb); |
3674d8e6 AM |
1395 | const_bitmap equiv2 = equiv_set (ssa2, bb); |
1396 | if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1)) | |
ade5531c | 1397 | return VREL_EQ; |
3aaa69e5 | 1398 | |
b5563410 AM |
1399 | kind = partial_equiv (ssa1, ssa2); |
1400 | if (kind != VREL_VARYING) | |
1401 | return kind; | |
1402 | ||
3aaa69e5 AM |
1403 | // Initially look for a direct relationship and just return that. |
1404 | kind = find_relation_dom (bb, v1, v2); | |
ade5531c | 1405 | if (kind != VREL_VARYING) |
3aaa69e5 AM |
1406 | return kind; |
1407 | ||
1d2aa262 | 1408 | // Query using the equivalence sets. |
fca649de | 1409 | kind = query (bb, equiv1, equiv2); |
3aaa69e5 AM |
1410 | return kind; |
1411 | } | |
1412 | ||
1413 | // Dump all the relations in block BB to file F. | |
1414 | ||
1415 | void | |
3674d8e6 | 1416 | dom_oracle::dump (FILE *f, basic_block bb) const |
3aaa69e5 AM |
1417 | { |
1418 | equiv_oracle::dump (f,bb); | |
1419 | ||
1420 | if (bb->index >= (int)m_relations.length ()) | |
1421 | return; | |
1422 | if (!m_relations[bb->index].m_names) | |
1423 | return; | |
1424 | ||
1425 | relation_chain *ptr = m_relations[bb->index].m_head; | |
1426 | for (; ptr; ptr = ptr->m_next) | |
1427 | { | |
1428 | fprintf (f, "Relational : "); | |
1429 | ptr->dump (f); | |
1430 | fprintf (f, "\n"); | |
1431 | } | |
1432 | } | |
1433 | ||
1434 | // Dump all the relations known to file F. | |
1435 | ||
1436 | void | |
3674d8e6 | 1437 | dom_oracle::dump (FILE *f) const |
3aaa69e5 AM |
1438 | { |
1439 | fprintf (f, "Relation dump\n"); | |
1440 | for (unsigned i = 0; i < m_relations.length (); i++) | |
ce0b409f AM |
1441 | if (BASIC_BLOCK_FOR_FN (cfun, i)) |
1442 | { | |
1443 | fprintf (f, "BB%d\n", i); | |
1444 | dump (f, BASIC_BLOCK_FOR_FN (cfun, i)); | |
1445 | } | |
3aaa69e5 | 1446 | } |
abcd2373 AH |
1447 | |
1448 | void | |
1449 | relation_oracle::debug () const | |
1450 | { | |
1451 | dump (stderr); | |
1452 | } | |
534c5352 AM |
1453 | |
1454 | path_oracle::path_oracle (relation_oracle *oracle) | |
1455 | { | |
eb5ee646 | 1456 | set_root_oracle (oracle); |
534c5352 AM |
1457 | bitmap_obstack_initialize (&m_bitmaps); |
1458 | obstack_init (&m_chain_obstack); | |
1459 | ||
1460 | // Initialize header records. | |
1461 | m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps); | |
1462 | m_equiv.m_bb = NULL; | |
1463 | m_equiv.m_next = NULL; | |
1464 | m_relations.m_names = BITMAP_ALLOC (&m_bitmaps); | |
1465 | m_relations.m_head = NULL; | |
4856699e | 1466 | m_killed_defs = BITMAP_ALLOC (&m_bitmaps); |
534c5352 AM |
1467 | } |
1468 | ||
1469 | path_oracle::~path_oracle () | |
1470 | { | |
1471 | obstack_free (&m_chain_obstack, NULL); | |
1472 | bitmap_obstack_release (&m_bitmaps); | |
1473 | } | |
1474 | ||
1475 | // Return the equiv set for SSA, and if there isn't one, check for equivs | |
1476 | // starting in block BB. | |
1477 | ||
1478 | const_bitmap | |
1479 | path_oracle::equiv_set (tree ssa, basic_block bb) | |
1480 | { | |
1481 | // Check the list first. | |
1482 | equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa)); | |
1483 | if (ptr) | |
1484 | return ptr->m_names; | |
1485 | ||
1486 | // Otherwise defer to the root oracle. | |
1487 | if (m_root) | |
1488 | return m_root->equiv_set (ssa, bb); | |
1489 | ||
1490 | // Allocate a throw away bitmap if there isn't a root oracle. | |
1491 | bitmap tmp = BITMAP_ALLOC (&m_bitmaps); | |
1492 | bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa)); | |
1493 | return tmp; | |
1494 | } | |
1495 | ||
c46b5b0a | 1496 | // Register an equivalence between SSA1 and SSA2 resolving unknowns from |
534c5352 AM |
1497 | // block BB. |
1498 | ||
1499 | void | |
1500 | path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2) | |
1501 | { | |
1502 | const_bitmap equiv_1 = equiv_set (ssa1, bb); | |
1503 | const_bitmap equiv_2 = equiv_set (ssa2, bb); | |
1504 | ||
1505 | // Check if they are the same set, if so, we're done. | |
1506 | if (bitmap_equal_p (equiv_1, equiv_2)) | |
1507 | return; | |
1508 | ||
1509 | // Don't mess around, simply create a new record and insert it first. | |
1510 | bitmap b = BITMAP_ALLOC (&m_bitmaps); | |
6b73c07e AM |
1511 | valid_equivs (b, equiv_1, bb); |
1512 | valid_equivs (b, equiv_2, bb); | |
534c5352 AM |
1513 | |
1514 | equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, | |
1515 | sizeof (equiv_chain)); | |
1516 | ptr->m_names = b; | |
1517 | ptr->m_bb = NULL; | |
1518 | ptr->m_next = m_equiv.m_next; | |
1519 | m_equiv.m_next = ptr; | |
1520 | bitmap_ior_into (m_equiv.m_names, b); | |
1521 | } | |
1522 | ||
8a0fadda AH |
1523 | // Register killing definition of an SSA_NAME. |
1524 | ||
1525 | void | |
1526 | path_oracle::killing_def (tree ssa) | |
1527 | { | |
1528 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1529 | { | |
1530 | fprintf (dump_file, " Registering killing_def (path_oracle) "); | |
1531 | print_generic_expr (dump_file, ssa, TDF_SLIM); | |
1532 | fprintf (dump_file, "\n"); | |
1533 | } | |
1534 | ||
9f4edfc1 | 1535 | unsigned v = SSA_NAME_VERSION (ssa); |
9f4edfc1 | 1536 | |
4856699e | 1537 | bitmap_set_bit (m_killed_defs, v); |
19ffb35d | 1538 | bitmap_set_bit (m_equiv.m_names, v); |
dc173a43 AH |
1539 | |
1540 | // Now add an equivalency with itself so we don't look to the root oracle. | |
1541 | bitmap b = BITMAP_ALLOC (&m_bitmaps); | |
1542 | bitmap_set_bit (b, v); | |
1543 | equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, | |
1544 | sizeof (equiv_chain)); | |
1545 | ptr->m_names = b; | |
1546 | ptr->m_bb = NULL; | |
1547 | ptr->m_next = m_equiv.m_next; | |
1548 | m_equiv.m_next = ptr; | |
6ef9ad93 AH |
1549 | |
1550 | // Walk the relation list and remove SSA from any relations. | |
9f4edfc1 AH |
1551 | if (!bitmap_bit_p (m_relations.m_names, v)) |
1552 | return; | |
1553 | ||
1554 | bitmap_clear_bit (m_relations.m_names, v); | |
1555 | relation_chain **prev = &(m_relations.m_head); | |
1556 | relation_chain *next = NULL; | |
1557 | for (relation_chain *ptr = m_relations.m_head; ptr; ptr = next) | |
1558 | { | |
1559 | gcc_checking_assert (*prev == ptr); | |
1560 | next = ptr->m_next; | |
1561 | if (SSA_NAME_VERSION (ptr->op1 ()) == v | |
1562 | || SSA_NAME_VERSION (ptr->op2 ()) == v) | |
1563 | *prev = ptr->m_next; | |
1564 | else | |
1565 | prev = &(ptr->m_next); | |
1566 | } | |
8a0fadda AH |
1567 | } |
1568 | ||
534c5352 AM |
1569 | // Register relation K between SSA1 and SSA2, resolving unknowns by |
1570 | // querying from BB. | |
1571 | ||
1572 | void | |
fca649de | 1573 | path_oracle::record (basic_block bb, relation_kind k, tree ssa1, tree ssa2) |
534c5352 | 1574 | { |
4a36b4e1 AH |
1575 | // If the 2 ssa_names are the same, do nothing. An equivalence is implied, |
1576 | // and no other relation makes sense. | |
1577 | if (ssa1 == ssa2) | |
1578 | return; | |
1579 | ||
534c5352 AM |
1580 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1581 | { | |
1582 | value_relation vr (k, ssa1, ssa2); | |
1583 | fprintf (dump_file, " Registering value_relation (path_oracle) "); | |
1584 | vr.dump (dump_file); | |
eb5ee646 | 1585 | fprintf (dump_file, " (root: bb%d)\n", bb->index); |
534c5352 AM |
1586 | } |
1587 | ||
fca649de | 1588 | relation_kind curr = query (bb, ssa1, ssa2); |
6101a276 AM |
1589 | if (curr != VREL_VARYING) |
1590 | k = relation_intersect (curr, k); | |
1591 | ||
ade5531c | 1592 | if (k == VREL_EQ) |
534c5352 AM |
1593 | { |
1594 | register_equiv (bb, ssa1, ssa2); | |
1595 | return; | |
1596 | } | |
1597 | ||
534c5352 AM |
1598 | bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1)); |
1599 | bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2)); | |
1600 | relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack, | |
1601 | sizeof (relation_chain)); | |
1602 | ptr->set_relation (k, ssa1, ssa2); | |
1603 | ptr->m_next = m_relations.m_head; | |
1604 | m_relations.m_head = ptr; | |
1605 | } | |
1606 | ||
1607 | // Query for a relationship between equiv set B1 and B2, resolving unknowns | |
1608 | // starting at block BB. | |
1609 | ||
1610 | relation_kind | |
fca649de | 1611 | path_oracle::query (basic_block bb, const_bitmap b1, const_bitmap b2) |
534c5352 AM |
1612 | { |
1613 | if (bitmap_equal_p (b1, b2)) | |
ade5531c | 1614 | return VREL_EQ; |
534c5352 AM |
1615 | |
1616 | relation_kind k = m_relations.find_relation (b1, b2); | |
1617 | ||
4856699e AH |
1618 | // Do not look at the root oracle for names that have been killed |
1619 | // along the path. | |
1620 | if (bitmap_intersect_p (m_killed_defs, b1) | |
1621 | || bitmap_intersect_p (m_killed_defs, b2)) | |
1622 | return k; | |
1623 | ||
ade5531c | 1624 | if (k == VREL_VARYING && m_root) |
fca649de | 1625 | k = m_root->query (bb, b1, b2); |
534c5352 AM |
1626 | |
1627 | return k; | |
1628 | } | |
1629 | ||
1630 | // Query for a relationship between SSA1 and SSA2, resolving unknowns | |
1631 | // starting at block BB. | |
1632 | ||
1633 | relation_kind | |
fca649de | 1634 | path_oracle::query (basic_block bb, tree ssa1, tree ssa2) |
534c5352 AM |
1635 | { |
1636 | unsigned v1 = SSA_NAME_VERSION (ssa1); | |
1637 | unsigned v2 = SSA_NAME_VERSION (ssa2); | |
1638 | ||
1639 | if (v1 == v2) | |
ade5531c | 1640 | return VREL_EQ; |
534c5352 AM |
1641 | |
1642 | const_bitmap equiv_1 = equiv_set (ssa1, bb); | |
1643 | const_bitmap equiv_2 = equiv_set (ssa2, bb); | |
1644 | if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1)) | |
ade5531c | 1645 | return VREL_EQ; |
534c5352 | 1646 | |
fca649de | 1647 | return query (bb, equiv_1, equiv_2); |
534c5352 AM |
1648 | } |
1649 | ||
5adfb654 AH |
1650 | // Reset any relations registered on this path. ORACLE is the root |
1651 | // oracle to use. | |
534c5352 AM |
1652 | |
1653 | void | |
5adfb654 | 1654 | path_oracle::reset_path (relation_oracle *oracle) |
534c5352 | 1655 | { |
5adfb654 | 1656 | set_root_oracle (oracle); |
534c5352 AM |
1657 | m_equiv.m_next = NULL; |
1658 | bitmap_clear (m_equiv.m_names); | |
1659 | m_relations.m_head = NULL; | |
1660 | bitmap_clear (m_relations.m_names); | |
602a3161 | 1661 | bitmap_clear (m_killed_defs); |
534c5352 AM |
1662 | } |
1663 | ||
1664 | // Dump relation in basic block... Do nothing here. | |
1665 | ||
1666 | void | |
1667 | path_oracle::dump (FILE *, basic_block) const | |
1668 | { | |
1669 | } | |
1670 | ||
1671 | // Dump the relations and equivalencies found in the path. | |
1672 | ||
1673 | void | |
1674 | path_oracle::dump (FILE *f) const | |
1675 | { | |
1676 | equiv_chain *ptr = m_equiv.m_next; | |
2fc9b4d7 AH |
1677 | relation_chain *ptr2 = m_relations.m_head; |
1678 | ||
1679 | if (ptr || ptr2) | |
1680 | fprintf (f, "\npath_oracle:\n"); | |
1681 | ||
534c5352 AM |
1682 | for (; ptr; ptr = ptr->m_next) |
1683 | ptr->dump (f); | |
1684 | ||
534c5352 AM |
1685 | for (; ptr2; ptr2 = ptr2->m_next) |
1686 | { | |
1687 | fprintf (f, "Relational : "); | |
1688 | ptr2->dump (f); | |
1689 | fprintf (f, "\n"); | |
1690 | } | |
1691 | } | |
aa05838b AM |
1692 | |
1693 | // ------------------------------------------------------------------------ | |
1694 | // EQUIV iterator. Although we have bitmap iterators, don't expose that it | |
1695 | // is currently a bitmap. Use an export iterator to hide future changes. | |
1696 | ||
1697 | // Construct a basic iterator over an equivalence bitmap. | |
1698 | ||
1699 | equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle, | |
1700 | basic_block bb, tree name, | |
1701 | bool full, bool partial) | |
1702 | { | |
1703 | m_name = name; | |
1704 | m_oracle = oracle; | |
1705 | m_pe = partial ? oracle->partial_equiv_set (name) : NULL; | |
1706 | m_bm = NULL; | |
1707 | if (full) | |
1708 | m_bm = oracle->equiv_set (name, bb); | |
1709 | if (!m_bm && m_pe) | |
1710 | m_bm = m_pe->members; | |
1711 | if (m_bm) | |
1712 | bmp_iter_set_init (&m_bi, m_bm, 1, &m_y); | |
1713 | } | |
1714 | ||
1715 | // Move to the next export bitmap spot. | |
1716 | ||
1717 | void | |
1718 | equiv_relation_iterator::next () | |
1719 | { | |
1720 | bmp_iter_next (&m_bi, &m_y); | |
1721 | } | |
1722 | ||
1723 | // Fetch the name of the next export in the export list. Return NULL if | |
1724 | // iteration is done. | |
1725 | ||
1726 | tree | |
1727 | equiv_relation_iterator::get_name (relation_kind *rel) | |
1728 | { | |
1729 | if (!m_bm) | |
1730 | return NULL_TREE; | |
1731 | ||
1732 | while (bmp_iter_set (&m_bi, &m_y)) | |
1733 | { | |
1734 | // Do not return self. | |
1735 | tree t = ssa_name (m_y); | |
1736 | if (t && t != m_name) | |
1737 | { | |
1738 | relation_kind k = VREL_EQ; | |
1739 | if (m_pe && m_bm == m_pe->members) | |
1740 | { | |
1741 | const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t); | |
1742 | if (equiv_pe && equiv_pe->members == m_pe->members) | |
1743 | k = pe_min (m_pe->code, equiv_pe->code); | |
1744 | else | |
1745 | k = VREL_VARYING; | |
1746 | } | |
1747 | if (relation_equiv_p (k)) | |
1748 | { | |
1749 | if (rel) | |
1750 | *rel = k; | |
1751 | return t; | |
1752 | } | |
1753 | } | |
1754 | next (); | |
1755 | } | |
1756 | ||
1757 | // Process partial equivs after full equivs if both were requested. | |
1758 | if (m_pe && m_bm != m_pe->members) | |
1759 | { | |
1760 | m_bm = m_pe->members; | |
1761 | if (m_bm) | |
1762 | { | |
1763 | // Recursively call back to process First PE. | |
1764 | bmp_iter_set_init (&m_bi, m_bm, 1, &m_y); | |
1765 | return get_name (rel); | |
1766 | } | |
1767 | } | |
1768 | return NULL_TREE; | |
1769 | } | |
c81e68a9 JJ |
1770 | |
1771 | #if CHECKING_P | |
1772 | #include "selftest.h" | |
1773 | ||
1774 | namespace selftest | |
1775 | { | |
1776 | void | |
1777 | relation_tests () | |
1778 | { | |
0cdb609f JJ |
1779 | // rr_*_table tables use unsigned char rather than relation_kind. |
1780 | ASSERT_LT (VREL_LAST, UCHAR_MAX); | |
c81e68a9 JJ |
1781 | // Verify commutativity of relation_intersect and relation_union. |
1782 | for (relation_kind r1 = VREL_VARYING; r1 < VREL_PE8; | |
1783 | r1 = relation_kind (r1 + 1)) | |
1784 | for (relation_kind r2 = VREL_VARYING; r2 < VREL_PE8; | |
1785 | r2 = relation_kind (r2 + 1)) | |
1786 | { | |
1787 | ASSERT_EQ (relation_intersect (r1, r2), relation_intersect (r2, r1)); | |
1788 | ASSERT_EQ (relation_union (r1, r2), relation_union (r2, r1)); | |
1789 | } | |
1790 | } | |
1791 | ||
1792 | } // namespace selftest | |
1793 | ||
1794 | #endif // CHECKING_P |