]>
Commit | Line | Data |
---|---|---|
fcc7c636 | 1 | /* Basic block path solver. |
7adcbafe | 2 | Copyright (C) 2021-2022 Free Software Foundation, Inc. |
fcc7c636 AH |
3 | Contributed by Aldy Hernandez <aldyh@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 "cfganal.h" | |
28 | #include "value-range.h" | |
29 | #include "gimple-range.h" | |
30 | #include "tree-pretty-print.h" | |
31 | #include "gimple-range-path.h" | |
32 | #include "ssa.h" | |
f46d3363 AH |
33 | #include "tree-cfg.h" |
34 | #include "gimple-iterator.h" | |
fcc7c636 AH |
35 | |
36 | // Internal construct to help facilitate debugging of solver. | |
47c2cf3a | 37 | #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL)) |
fcc7c636 | 38 | |
dc777f6b | 39 | path_range_query::path_range_query (bool resolve, gimple_ranger *ranger) |
53b3edce AH |
40 | : m_cache (new ssa_global_cache), |
41 | m_has_cache_entry (BITMAP_ALLOC (NULL)), | |
53b3edce | 42 | m_resolve (resolve), |
dc777f6b | 43 | m_alloced_ranger (!ranger) |
fcc7c636 | 44 | { |
dc777f6b AH |
45 | if (m_alloced_ranger) |
46 | m_ranger = new gimple_ranger; | |
47 | else | |
48 | m_ranger = ranger; | |
53b3edce | 49 | |
53b3edce | 50 | m_oracle = new path_oracle (m_ranger->oracle ()); |
83ad3a96 AH |
51 | |
52 | if (m_resolve && flag_checking) | |
53 | verify_marked_backedges (cfun); | |
fcc7c636 AH |
54 | } |
55 | ||
56 | path_range_query::~path_range_query () | |
57 | { | |
f46d3363 | 58 | delete m_oracle; |
53b3edce AH |
59 | if (m_alloced_ranger) |
60 | delete m_ranger; | |
dc777f6b AH |
61 | BITMAP_FREE (m_has_cache_entry); |
62 | delete m_cache; | |
63 | } | |
64 | ||
65 | // Return TRUE if NAME is in the import bitmap. | |
66 | ||
67 | bool | |
68 | path_range_query::import_p (tree name) | |
69 | { | |
70 | return (TREE_CODE (name) == SSA_NAME | |
71 | && bitmap_bit_p (m_imports, SSA_NAME_VERSION (name))); | |
fcc7c636 AH |
72 | } |
73 | ||
74 | // Mark cache entry for NAME as unused. | |
75 | ||
76 | void | |
77 | path_range_query::clear_cache (tree name) | |
78 | { | |
79 | unsigned v = SSA_NAME_VERSION (name); | |
80 | bitmap_clear_bit (m_has_cache_entry, v); | |
81 | } | |
82 | ||
83 | // If NAME has a cache entry, return it in R, and return TRUE. | |
84 | ||
85 | inline bool | |
45c8523d | 86 | path_range_query::get_cache (vrange &r, tree name) |
fcc7c636 AH |
87 | { |
88 | if (!gimple_range_ssa_p (name)) | |
89 | return get_global_range_query ()->range_of_expr (r, name); | |
90 | ||
91 | unsigned v = SSA_NAME_VERSION (name); | |
92 | if (bitmap_bit_p (m_has_cache_entry, v)) | |
93 | return m_cache->get_global_range (r, name); | |
94 | ||
95 | return false; | |
96 | } | |
97 | ||
98 | // Set the cache entry for NAME to R. | |
99 | ||
100 | void | |
45c8523d | 101 | path_range_query::set_cache (const vrange &r, tree name) |
fcc7c636 AH |
102 | { |
103 | unsigned v = SSA_NAME_VERSION (name); | |
104 | bitmap_set_bit (m_has_cache_entry, v); | |
105 | m_cache->set_global_range (name, r); | |
106 | } | |
107 | ||
108 | void | |
109 | path_range_query::dump (FILE *dump_file) | |
110 | { | |
8d42a27d AH |
111 | push_dump_file save (dump_file, dump_flags & ~TDF_DETAILS); |
112 | ||
b0c83d59 | 113 | if (m_path.is_empty ()) |
fcc7c636 AH |
114 | return; |
115 | ||
116 | unsigned i; | |
117 | bitmap_iterator bi; | |
fcc7c636 | 118 | |
b0c83d59 | 119 | dump_ranger (dump_file, m_path); |
fcc7c636 AH |
120 | |
121 | fprintf (dump_file, "Imports:\n"); | |
122 | EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi) | |
123 | { | |
124 | tree name = ssa_name (i); | |
125 | print_generic_expr (dump_file, name, TDF_SLIM); | |
126 | fprintf (dump_file, "\n"); | |
127 | } | |
128 | ||
129 | m_cache->dump (dump_file); | |
130 | } | |
131 | ||
132 | void | |
133 | path_range_query::debug () | |
134 | { | |
135 | dump (stderr); | |
136 | } | |
137 | ||
97cfb54c AH |
138 | // Return TRUE if NAME is defined outside the current path. |
139 | ||
140 | bool | |
141 | path_range_query::defined_outside_path (tree name) | |
142 | { | |
143 | gimple *def = SSA_NAME_DEF_STMT (name); | |
144 | basic_block bb = gimple_bb (def); | |
145 | ||
b0c83d59 | 146 | return !bb || !m_path.contains (bb); |
97cfb54c AH |
147 | } |
148 | ||
149 | // Return the range of NAME on entry to the path. | |
150 | ||
151 | void | |
45c8523d | 152 | path_range_query::range_on_path_entry (vrange &r, tree name) |
97cfb54c | 153 | { |
a311163f | 154 | gcc_checking_assert (defined_outside_path (name)); |
97cfb54c | 155 | basic_block entry = entry_bb (); |
fb8b72eb | 156 | |
6a9678f0 AH |
157 | // Prefer to use range_of_expr if we have a statement to look at, |
158 | // since it has better caching than range_on_edge. | |
159 | gimple *last = last_stmt (entry); | |
160 | if (last) | |
161 | { | |
53b3edce | 162 | if (m_ranger->range_of_expr (r, name, last)) |
6a9678f0 AH |
163 | return; |
164 | gcc_unreachable (); | |
165 | } | |
166 | ||
167 | // If we have no statement, look at all the incoming ranges to the | |
168 | // block. This can happen when we're querying a block with only an | |
169 | // outgoing edge (no statement but the fall through edge), but for | |
170 | // which we can determine a range on entry to the block. | |
45c8523d | 171 | Value_Range tmp (TREE_TYPE (name)); |
6a9678f0 | 172 | bool changed = false; |
97cfb54c AH |
173 | r.set_undefined (); |
174 | for (unsigned i = 0; i < EDGE_COUNT (entry->preds); ++i) | |
175 | { | |
176 | edge e = EDGE_PRED (entry, i); | |
177 | if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) | |
53b3edce | 178 | && m_ranger->range_on_edge (tmp, e, name)) |
fb8b72eb AH |
179 | { |
180 | r.union_ (tmp); | |
181 | changed = true; | |
182 | } | |
97cfb54c | 183 | } |
fb8b72eb AH |
184 | |
185 | // Make sure we don't return UNDEFINED by mistake. | |
186 | if (!changed) | |
187 | r.set_varying (TREE_TYPE (name)); | |
97cfb54c AH |
188 | } |
189 | ||
fcc7c636 AH |
190 | // Return the range of NAME at the end of the path being analyzed. |
191 | ||
192 | bool | |
45c8523d | 193 | path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt) |
fcc7c636 | 194 | { |
45c8523d | 195 | if (!vrange::supports_type_p (TREE_TYPE (name))) |
fcc7c636 AH |
196 | return false; |
197 | ||
198 | if (get_cache (r, name)) | |
199 | return true; | |
200 | ||
97cfb54c AH |
201 | if (m_resolve && defined_outside_path (name)) |
202 | { | |
203 | range_on_path_entry (r, name); | |
97cfb54c AH |
204 | set_cache (r, name); |
205 | return true; | |
206 | } | |
fcc7c636 | 207 | |
fcdf49a0 AH |
208 | if (stmt |
209 | && range_defined_in_block (r, name, gimple_bb (stmt))) | |
fcc7c636 | 210 | { |
01b50387 | 211 | if (TREE_CODE (name) == SSA_NAME) |
45c8523d AH |
212 | { |
213 | Value_Range glob (TREE_TYPE (name)); | |
214 | gimple_range_global (glob, name); | |
215 | r.intersect (glob); | |
216 | } | |
01b50387 | 217 | |
fcc7c636 AH |
218 | set_cache (r, name); |
219 | return true; | |
220 | } | |
221 | ||
45c8523d | 222 | gimple_range_global (r, name); |
fcc7c636 AH |
223 | return true; |
224 | } | |
225 | ||
90ef1535 | 226 | bool |
45c8523d | 227 | path_range_query::range_of_expr (vrange &r, tree name, gimple *stmt) |
90ef1535 AH |
228 | { |
229 | if (internal_range_of_expr (r, name, stmt)) | |
230 | { | |
231 | if (r.undefined_p ()) | |
232 | m_undefined_path = true; | |
233 | ||
234 | return true; | |
235 | } | |
236 | return false; | |
237 | } | |
238 | ||
239 | bool | |
240 | path_range_query::unreachable_path_p () | |
241 | { | |
242 | return m_undefined_path; | |
243 | } | |
244 | ||
fcc7c636 AH |
245 | // Initialize the current path to PATH. The current block is set to |
246 | // the entry block to the path. | |
247 | // | |
248 | // Note that the blocks are in reverse order, so the exit block is | |
249 | // path[0]. | |
250 | ||
251 | void | |
252 | path_range_query::set_path (const vec<basic_block> &path) | |
253 | { | |
254 | gcc_checking_assert (path.length () > 1); | |
b0c83d59 AH |
255 | m_path = path.copy (); |
256 | m_pos = m_path.length () - 1; | |
fcc7c636 AH |
257 | bitmap_clear (m_has_cache_entry); |
258 | } | |
259 | ||
fcdf49a0 AH |
260 | bool |
261 | path_range_query::ssa_defined_in_bb (tree name, basic_block bb) | |
262 | { | |
263 | return (TREE_CODE (name) == SSA_NAME | |
264 | && SSA_NAME_DEF_STMT (name) | |
265 | && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb); | |
266 | } | |
267 | ||
fcc7c636 | 268 | // Return the range of the result of PHI in R. |
fcdf49a0 AH |
269 | // |
270 | // Since PHIs are calculated in parallel at the beginning of the | |
271 | // block, we must be careful to never save anything to the cache here. | |
272 | // It is the caller's responsibility to adjust the cache. Also, | |
273 | // calculating the PHI's range must not trigger additional lookups. | |
fcc7c636 AH |
274 | |
275 | void | |
45c8523d | 276 | path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) |
fcc7c636 AH |
277 | { |
278 | tree name = gimple_phi_result (phi); | |
279 | basic_block bb = gimple_bb (phi); | |
fcdf49a0 | 280 | unsigned nargs = gimple_phi_num_args (phi); |
fcc7c636 | 281 | |
fcc7c636 AH |
282 | if (at_entry ()) |
283 | { | |
53b3edce | 284 | if (m_resolve && m_ranger->range_of_expr (r, name, phi)) |
97cfb54c AH |
285 | return; |
286 | ||
fcdf49a0 AH |
287 | // Try to fold the phi exclusively with global or cached values. |
288 | // This will get things like PHI <5(99), 6(88)>. We do this by | |
289 | // calling range_of_expr with no context. | |
45c8523d | 290 | Value_Range arg_range (TREE_TYPE (name)); |
fcdf49a0 AH |
291 | r.set_undefined (); |
292 | for (size_t i = 0; i < nargs; ++i) | |
293 | { | |
294 | tree arg = gimple_phi_arg_def (phi, i); | |
295 | if (range_of_expr (arg_range, arg, /*stmt=*/NULL)) | |
296 | r.union_ (arg_range); | |
297 | else | |
298 | { | |
299 | r.set_varying (TREE_TYPE (name)); | |
300 | return; | |
301 | } | |
302 | } | |
fcc7c636 AH |
303 | return; |
304 | } | |
305 | ||
306 | basic_block prev = prev_bb (); | |
307 | edge e_in = find_edge (prev, bb); | |
fcc7c636 AH |
308 | |
309 | for (size_t i = 0; i < nargs; ++i) | |
310 | if (e_in == gimple_phi_arg_edge (phi, i)) | |
311 | { | |
312 | tree arg = gimple_phi_arg_def (phi, i); | |
fcdf49a0 AH |
313 | // Avoid using the cache for ARGs defined in this block, as |
314 | // that could create an ordering problem. | |
315 | if (ssa_defined_in_bb (arg, bb) || !get_cache (r, arg)) | |
97cfb54c AH |
316 | { |
317 | if (m_resolve) | |
318 | { | |
45c8523d | 319 | Value_Range tmp (TREE_TYPE (name)); |
97cfb54c AH |
320 | // Using both the range on entry to the path, and the |
321 | // range on this edge yields significantly better | |
322 | // results. | |
a311163f AH |
323 | if (defined_outside_path (arg)) |
324 | range_on_path_entry (r, arg); | |
325 | else | |
326 | r.set_varying (TREE_TYPE (name)); | |
53b3edce | 327 | m_ranger->range_on_edge (tmp, e_in, arg); |
97cfb54c AH |
328 | r.intersect (tmp); |
329 | return; | |
330 | } | |
331 | r.set_varying (TREE_TYPE (name)); | |
332 | } | |
fcc7c636 AH |
333 | return; |
334 | } | |
335 | gcc_unreachable (); | |
336 | } | |
337 | ||
338 | // If NAME is defined in BB, set R to the range of NAME, and return | |
339 | // TRUE. Otherwise, return FALSE. | |
340 | ||
341 | bool | |
45c8523d | 342 | path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb) |
fcc7c636 AH |
343 | { |
344 | gimple *def_stmt = SSA_NAME_DEF_STMT (name); | |
345 | basic_block def_bb = gimple_bb (def_stmt); | |
346 | ||
347 | if (def_bb != bb) | |
348 | return false; | |
349 | ||
18546941 AH |
350 | if (get_cache (r, name)) |
351 | return true; | |
352 | ||
fcc7c636 AH |
353 | if (gimple_code (def_stmt) == GIMPLE_PHI) |
354 | ssa_range_in_phi (r, as_a<gphi *> (def_stmt)); | |
aeb10f8d AH |
355 | else |
356 | { | |
357 | if (name) | |
358 | get_path_oracle ()->killing_def (name); | |
359 | ||
360 | if (!range_of_stmt (r, def_stmt, name)) | |
361 | r.set_varying (TREE_TYPE (name)); | |
362 | } | |
fcc7c636 | 363 | |
b7501739 AM |
364 | if (bb && POINTER_TYPE_P (TREE_TYPE (name))) |
365 | m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb); | |
410e8742 | 366 | |
5db93cd0 | 367 | if (DEBUG_SOLVER && (bb || !r.varying_p ())) |
fcc7c636 | 368 | { |
5db93cd0 | 369 | fprintf (dump_file, "range_defined_in_block (BB%d) for ", bb ? bb->index : -1); |
fcc7c636 AH |
370 | print_generic_expr (dump_file, name, TDF_SLIM); |
371 | fprintf (dump_file, " is "); | |
372 | r.dump (dump_file); | |
373 | fprintf (dump_file, "\n"); | |
374 | } | |
5db93cd0 | 375 | |
fcc7c636 AH |
376 | return true; |
377 | } | |
378 | ||
b7a23949 AH |
379 | // Compute ranges defined in the PHIs in this block. |
380 | ||
381 | void | |
382 | path_range_query::compute_ranges_in_phis (basic_block bb) | |
383 | { | |
54ebec35 | 384 | auto_bitmap phi_set; |
b7a23949 AH |
385 | |
386 | // PHIs must be resolved simultaneously on entry to the block | |
387 | // because any dependencies must be satistifed with values on entry. | |
388 | // Thus, we calculate all PHIs first, and then update the cache at | |
389 | // the end. | |
390 | ||
54ebec35 | 391 | for (auto iter = gsi_start_phis (bb); !gsi_end_p (iter); gsi_next (&iter)) |
b7a23949 AH |
392 | { |
393 | gphi *phi = iter.phi (); | |
394 | tree name = gimple_phi_result (phi); | |
395 | ||
45c8523d AH |
396 | if (!import_p (name)) |
397 | continue; | |
398 | ||
399 | Value_Range r (TREE_TYPE (name)); | |
400 | if (range_defined_in_block (r, name, bb)) | |
54ebec35 AH |
401 | { |
402 | unsigned v = SSA_NAME_VERSION (name); | |
403 | set_cache (r, name); | |
404 | bitmap_set_bit (phi_set, v); | |
405 | // Pretend we don't have a cache entry for this name until | |
406 | // we're done with all PHIs. | |
407 | bitmap_clear_bit (m_has_cache_entry, v); | |
408 | } | |
b7a23949 | 409 | } |
54ebec35 | 410 | bitmap_ior_into (m_has_cache_entry, phi_set); |
b7a23949 AH |
411 | } |
412 | ||
eb5ee646 AH |
413 | // Return TRUE if relations may be invalidated after crossing edge E. |
414 | ||
415 | bool | |
416 | path_range_query::relations_may_be_invalidated (edge e) | |
417 | { | |
418 | // As soon as the path crosses a back edge, we can encounter | |
419 | // definitions of SSA_NAMEs that may have had a use in the path | |
420 | // already, so this will then be a new definition. The relation | |
421 | // code is all designed around seeing things in dominator order, and | |
422 | // crossing a back edge in the path violates this assumption. | |
423 | return (e->flags & EDGE_DFS_BACK); | |
424 | } | |
425 | ||
83668368 AH |
426 | // Compute ranges defined in the current block, or exported to the |
427 | // next block. | |
fcc7c636 AH |
428 | |
429 | void | |
83668368 | 430 | path_range_query::compute_ranges_in_block (basic_block bb) |
fcc7c636 AH |
431 | { |
432 | bitmap_iterator bi; | |
fcc7c636 AH |
433 | unsigned i; |
434 | ||
2f0b6a97 AH |
435 | if (m_resolve && !at_entry ()) |
436 | compute_phi_relations (bb, prev_bb ()); | |
437 | ||
fcc7c636 AH |
438 | // Force recalculation of any names in the cache that are defined in |
439 | // this block. This can happen on interdependent SSA/phis in loops. | |
440 | EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi) | |
441 | { | |
442 | tree name = ssa_name (i); | |
fcdf49a0 | 443 | if (ssa_defined_in_bb (name, bb)) |
fcc7c636 AH |
444 | clear_cache (name); |
445 | } | |
446 | ||
415f9ee4 AH |
447 | // Solve imports defined in this block, starting with the PHIs... |
448 | compute_ranges_in_phis (bb); | |
449 | // ...and then the rest of the imports. | |
450 | EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi) | |
451 | { | |
452 | tree name = ssa_name (i); | |
45c8523d | 453 | Value_Range r (TREE_TYPE (name)); |
415f9ee4 AH |
454 | |
455 | if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI | |
456 | && range_defined_in_block (r, name, bb)) | |
457 | set_cache (r, name); | |
458 | } | |
fcc7c636 AH |
459 | |
460 | if (at_exit ()) | |
461 | return; | |
462 | ||
463 | // Solve imports that are exported to the next block. | |
2f0b6a97 AH |
464 | basic_block next = next_bb (); |
465 | edge e = find_edge (bb, next); | |
eb5ee646 AH |
466 | |
467 | if (m_resolve && relations_may_be_invalidated (e)) | |
468 | { | |
469 | if (DEBUG_SOLVER) | |
470 | fprintf (dump_file, | |
471 | "Resetting relations as they may be invalidated in %d->%d.\n", | |
472 | e->src->index, e->dest->index); | |
473 | ||
474 | path_oracle *p = get_path_oracle (); | |
475 | p->reset_path (); | |
476 | // ?? Instead of nuking the root oracle altogether, we could | |
477 | // reset the path oracle to search for relations from the top of | |
478 | // the loop with the root oracle. Something for future development. | |
479 | p->set_root_oracle (nullptr); | |
480 | } | |
481 | ||
fcc7c636 AH |
482 | EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi) |
483 | { | |
484 | tree name = ssa_name (i); | |
53b3edce | 485 | gori_compute &g = m_ranger->gori (); |
fcc7c636 AH |
486 | bitmap exports = g.exports (bb); |
487 | ||
488 | if (bitmap_bit_p (exports, i)) | |
489 | { | |
45c8523d | 490 | Value_Range r (TREE_TYPE (name)); |
fcc7c636 AH |
491 | if (g.outgoing_edge_range_p (r, e, name, *this)) |
492 | { | |
45c8523d | 493 | Value_Range cached_range (TREE_TYPE (name)); |
fcc7c636 AH |
494 | if (get_cache (cached_range, name)) |
495 | r.intersect (cached_range); | |
496 | ||
497 | set_cache (r, name); | |
498 | if (DEBUG_SOLVER) | |
499 | { | |
500 | fprintf (dump_file, "outgoing_edge_range_p for "); | |
501 | print_generic_expr (dump_file, name, TDF_SLIM); | |
502 | fprintf (dump_file, " on edge %d->%d ", | |
503 | e->src->index, e->dest->index); | |
504 | fprintf (dump_file, "is "); | |
505 | r.dump (dump_file); | |
506 | fprintf (dump_file, "\n"); | |
507 | } | |
508 | } | |
509 | } | |
510 | } | |
2f0b6a97 AH |
511 | |
512 | if (m_resolve) | |
513 | compute_outgoing_relations (bb, next); | |
fcc7c636 AH |
514 | } |
515 | ||
410e8742 AH |
516 | // Adjust all pointer imports in BB with non-null information. |
517 | ||
518 | void | |
519 | path_range_query::adjust_for_non_null_uses (basic_block bb) | |
520 | { | |
521 | int_range_max r; | |
522 | bitmap_iterator bi; | |
523 | unsigned i; | |
524 | ||
525 | EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi) | |
526 | { | |
527 | tree name = ssa_name (i); | |
528 | ||
529 | if (!POINTER_TYPE_P (TREE_TYPE (name))) | |
530 | continue; | |
531 | ||
532 | if (get_cache (r, name)) | |
533 | { | |
534 | if (r.nonzero_p ()) | |
535 | continue; | |
536 | } | |
537 | else | |
538 | r.set_varying (TREE_TYPE (name)); | |
539 | ||
b7501739 | 540 | if (m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb)) |
410e8742 AH |
541 | set_cache (r, name); |
542 | } | |
543 | } | |
544 | ||
e4249b10 AH |
545 | // If NAME is a supported SSA_NAME, add it the bitmap in IMPORTS. |
546 | ||
547 | bool | |
548 | path_range_query::add_to_imports (tree name, bitmap imports) | |
549 | { | |
550 | if (TREE_CODE (name) == SSA_NAME | |
45c8523d | 551 | && vrange::supports_type_p (TREE_TYPE (name))) |
e4249b10 AH |
552 | return bitmap_set_bit (imports, SSA_NAME_VERSION (name)); |
553 | return false; | |
554 | } | |
555 | ||
bfa04d0e AH |
556 | // Compute the imports to the path ending in EXIT. These are |
557 | // essentially the SSA names used to calculate the final conditional | |
558 | // along the path. | |
e4249b10 | 559 | // |
bfa04d0e AH |
560 | // They are hints for the solver. Adding more elements doesn't slow |
561 | // us down, because we don't solve anything that doesn't appear in the | |
562 | // path. On the other hand, not having enough imports will limit what | |
563 | // we can solve. | |
e4249b10 AH |
564 | |
565 | void | |
bfa04d0e | 566 | path_range_query::compute_imports (bitmap imports, basic_block exit) |
e4249b10 | 567 | { |
bfa04d0e | 568 | // Start with the imports from the exit block... |
d1c1919e AH |
569 | gori_compute &gori = m_ranger->gori (); |
570 | bitmap r_imports = gori.imports (exit); | |
bfa04d0e AH |
571 | bitmap_copy (imports, r_imports); |
572 | ||
573 | auto_vec<tree> worklist (bitmap_count_bits (imports)); | |
e4249b10 AH |
574 | bitmap_iterator bi; |
575 | unsigned i; | |
bfa04d0e | 576 | EXECUTE_IF_SET_IN_BITMAP (imports, 0, i, bi) |
e4249b10 AH |
577 | { |
578 | tree name = ssa_name (i); | |
579 | worklist.quick_push (name); | |
580 | } | |
581 | ||
bfa04d0e | 582 | // ...and add any operands used to define these imports. |
e4249b10 AH |
583 | while (!worklist.is_empty ()) |
584 | { | |
585 | tree name = worklist.pop (); | |
586 | gimple *def_stmt = SSA_NAME_DEF_STMT (name); | |
587 | ||
588 | if (is_gimple_assign (def_stmt)) | |
589 | { | |
bfa04d0e | 590 | add_to_imports (gimple_assign_rhs1 (def_stmt), imports); |
e4249b10 | 591 | tree rhs = gimple_assign_rhs2 (def_stmt); |
bfa04d0e | 592 | if (rhs && add_to_imports (rhs, imports)) |
e4249b10 AH |
593 | worklist.safe_push (rhs); |
594 | rhs = gimple_assign_rhs3 (def_stmt); | |
bfa04d0e | 595 | if (rhs && add_to_imports (rhs, imports)) |
e4249b10 AH |
596 | worklist.safe_push (rhs); |
597 | } | |
598 | else if (gphi *phi = dyn_cast <gphi *> (def_stmt)) | |
599 | { | |
600 | for (size_t i = 0; i < gimple_phi_num_args (phi); ++i) | |
601 | { | |
602 | edge e = gimple_phi_arg_edge (phi, i); | |
603 | tree arg = gimple_phi_arg (phi, i)->def; | |
604 | ||
605 | if (TREE_CODE (arg) == SSA_NAME | |
b0c83d59 | 606 | && m_path.contains (e->src) |
bfa04d0e | 607 | && bitmap_set_bit (imports, SSA_NAME_VERSION (arg))) |
e4249b10 AH |
608 | worklist.safe_push (arg); |
609 | } | |
610 | } | |
611 | } | |
d1c1919e AH |
612 | // Exported booleans along the path, may help conditionals. |
613 | if (m_resolve) | |
614 | for (i = 0; i < m_path.length (); ++i) | |
615 | { | |
616 | basic_block bb = m_path[i]; | |
617 | tree name; | |
618 | FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) | |
619 | if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) | |
620 | bitmap_set_bit (imports, SSA_NAME_VERSION (name)); | |
621 | } | |
e4249b10 AH |
622 | } |
623 | ||
83668368 | 624 | // Compute the ranges for IMPORTS along PATH. |
fcc7c636 AH |
625 | // |
626 | // IMPORTS are the set of SSA names, any of which could potentially | |
b0c83d59 AH |
627 | // change the value of the final conditional in PATH. Default to the |
628 | // imports of the last block in the path if none is given. | |
fcc7c636 AH |
629 | |
630 | void | |
83668368 AH |
631 | path_range_query::compute_ranges (const vec<basic_block> &path, |
632 | const bitmap_head *imports) | |
fcc7c636 | 633 | { |
55b3299d | 634 | if (DEBUG_SOLVER) |
2fc9b4d7 | 635 | fprintf (dump_file, "\n==============================================\n"); |
55b3299d | 636 | |
fcc7c636 | 637 | set_path (path); |
90ef1535 | 638 | m_undefined_path = false; |
fcc7c636 | 639 | |
b0c83d59 AH |
640 | if (imports) |
641 | bitmap_copy (m_imports, imports); | |
642 | else | |
bfa04d0e | 643 | compute_imports (m_imports, exit_bb ()); |
b0c83d59 | 644 | |
f46d3363 | 645 | if (m_resolve) |
bfa04d0e | 646 | get_path_oracle ()->reset_path (); |
f46d3363 | 647 | |
fcc7c636 | 648 | if (DEBUG_SOLVER) |
13428914 | 649 | { |
2fc9b4d7 | 650 | fprintf (dump_file, "path_range_query: compute_ranges for path: "); |
13428914 AH |
651 | for (unsigned i = path.length (); i > 0; --i) |
652 | { | |
653 | basic_block bb = path[i - 1]; | |
2fc9b4d7 | 654 | fprintf (dump_file, "%d", bb->index); |
13428914 | 655 | if (i > 1) |
2fc9b4d7 | 656 | fprintf (dump_file, "->"); |
13428914 AH |
657 | } |
658 | fprintf (dump_file, "\n"); | |
659 | } | |
fcc7c636 AH |
660 | |
661 | while (1) | |
662 | { | |
663 | basic_block bb = curr_bb (); | |
664 | ||
83668368 | 665 | compute_ranges_in_block (bb); |
410e8742 | 666 | adjust_for_non_null_uses (bb); |
fcc7c636 AH |
667 | |
668 | if (at_exit ()) | |
669 | break; | |
670 | ||
671 | move_next (); | |
672 | } | |
673 | ||
674 | if (DEBUG_SOLVER) | |
2f0b6a97 | 675 | { |
2f0b6a97 | 676 | get_path_oracle ()->dump (dump_file); |
2f0b6a97 AH |
677 | dump (dump_file); |
678 | } | |
fcc7c636 | 679 | } |
f46d3363 | 680 | |
b0c83d59 AH |
681 | // Convenience function to compute ranges along a path consisting of |
682 | // E->SRC and E->DEST. | |
683 | ||
684 | void | |
685 | path_range_query::compute_ranges (edge e) | |
686 | { | |
687 | auto_vec<basic_block> bbs (2); | |
688 | bbs.quick_push (e->dest); | |
689 | bbs.quick_push (e->src); | |
690 | compute_ranges (bbs); | |
691 | } | |
692 | ||
f46d3363 AH |
693 | // A folding aid used to register and query relations along a path. |
694 | // When queried, it returns relations as they would appear on exit to | |
695 | // the path. | |
696 | // | |
697 | // Relations are registered on entry so the path_oracle knows which | |
698 | // block to query the root oracle at when a relation lies outside the | |
699 | // path. However, when queried we return the relation on exit to the | |
700 | // path, since the root_oracle ignores the registered. | |
701 | ||
702 | class jt_fur_source : public fur_depend | |
703 | { | |
704 | public: | |
705 | jt_fur_source (gimple *s, path_range_query *, gori_compute *, | |
706 | const vec<basic_block> &); | |
707 | relation_kind query_relation (tree op1, tree op2) override; | |
708 | void register_relation (gimple *, relation_kind, tree op1, tree op2) override; | |
709 | void register_relation (edge, relation_kind, tree op1, tree op2) override; | |
710 | private: | |
711 | basic_block m_entry; | |
712 | }; | |
713 | ||
714 | jt_fur_source::jt_fur_source (gimple *s, | |
715 | path_range_query *query, | |
716 | gori_compute *gori, | |
717 | const vec<basic_block> &path) | |
718 | : fur_depend (s, gori, query) | |
719 | { | |
720 | gcc_checking_assert (!path.is_empty ()); | |
721 | ||
722 | m_entry = path[path.length () - 1]; | |
723 | ||
724 | if (dom_info_available_p (CDI_DOMINATORS)) | |
725 | m_oracle = query->oracle (); | |
726 | else | |
727 | m_oracle = NULL; | |
728 | } | |
729 | ||
730 | // Ignore statement and register relation on entry to path. | |
731 | ||
732 | void | |
733 | jt_fur_source::register_relation (gimple *, relation_kind k, tree op1, tree op2) | |
734 | { | |
735 | if (m_oracle) | |
736 | m_oracle->register_relation (m_entry, k, op1, op2); | |
737 | } | |
738 | ||
739 | // Ignore edge and register relation on entry to path. | |
740 | ||
741 | void | |
742 | jt_fur_source::register_relation (edge, relation_kind k, tree op1, tree op2) | |
743 | { | |
744 | if (m_oracle) | |
745 | m_oracle->register_relation (m_entry, k, op1, op2); | |
746 | } | |
747 | ||
748 | relation_kind | |
749 | jt_fur_source::query_relation (tree op1, tree op2) | |
750 | { | |
751 | if (!m_oracle) | |
ade5531c | 752 | return VREL_VARYING; |
f46d3363 AH |
753 | |
754 | if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME) | |
ade5531c | 755 | return VREL_VARYING; |
f46d3363 AH |
756 | |
757 | return m_oracle->query_relation (m_entry, op1, op2); | |
758 | } | |
759 | ||
760 | // Return the range of STMT at the end of the path being analyzed. | |
761 | ||
762 | bool | |
45c8523d | 763 | path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree) |
f46d3363 AH |
764 | { |
765 | tree type = gimple_range_type (stmt); | |
766 | ||
45c8523d | 767 | if (!type || !vrange::supports_type_p (type)) |
f46d3363 AH |
768 | return false; |
769 | ||
fcdf49a0 AH |
770 | // If resolving unknowns, fold the statement making use of any |
771 | // relations along the path. | |
f46d3363 AH |
772 | if (m_resolve) |
773 | { | |
774 | fold_using_range f; | |
53b3edce | 775 | jt_fur_source src (stmt, this, &m_ranger->gori (), m_path); |
f46d3363 AH |
776 | if (!f.fold_stmt (r, stmt, src)) |
777 | r.set_varying (type); | |
778 | } | |
fcdf49a0 | 779 | // Otherwise, fold without relations. |
f46d3363 AH |
780 | else if (!fold_range (r, stmt, this)) |
781 | r.set_varying (type); | |
782 | ||
783 | return true; | |
784 | } | |
785 | ||
eb5ee646 AH |
786 | // If possible, register the relation on the incoming edge E into PHI. |
787 | ||
f46d3363 | 788 | void |
eb5ee646 | 789 | path_range_query::maybe_register_phi_relation (gphi *phi, edge e) |
f46d3363 | 790 | { |
eb5ee646 AH |
791 | tree arg = gimple_phi_arg_def (phi, e->dest_idx); |
792 | ||
793 | if (!gimple_range_ssa_p (arg)) | |
794 | return; | |
795 | ||
796 | if (relations_may_be_invalidated (e)) | |
797 | return; | |
798 | ||
2f0b6a97 AH |
799 | basic_block bb = gimple_bb (phi); |
800 | tree result = gimple_phi_result (phi); | |
f46d3363 | 801 | |
2f0b6a97 | 802 | // Avoid recording the equivalence if the arg is defined in this |
fcdf49a0 AH |
803 | // block, as that could create an ordering problem. |
804 | if (ssa_defined_in_bb (arg, bb)) | |
2f0b6a97 | 805 | return; |
f46d3363 | 806 | |
2f0b6a97 | 807 | if (dump_file && (dump_flags & TDF_DETAILS)) |
eb5ee646 | 808 | fprintf (dump_file, "maybe_register_phi_relation in bb%d:", bb->index); |
f46d3363 | 809 | |
2f0b6a97 | 810 | get_path_oracle ()->killing_def (result); |
ade5531c | 811 | m_oracle->register_relation (entry_bb (), VREL_EQ, arg, result); |
f46d3363 AH |
812 | } |
813 | ||
83668368 | 814 | // Compute relations for each PHI in BB. For example: |
f46d3363 AH |
815 | // |
816 | // x_5 = PHI<y_9(5),...> | |
817 | // | |
818 | // If the path flows through BB5, we can register that x_5 == y_9. | |
819 | ||
820 | void | |
83668368 | 821 | path_range_query::compute_phi_relations (basic_block bb, basic_block prev) |
f46d3363 AH |
822 | { |
823 | if (prev == NULL) | |
824 | return; | |
825 | ||
f46d3363 | 826 | edge e_in = find_edge (prev, bb); |
f46d3363 AH |
827 | |
828 | for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter); | |
829 | gsi_next (&iter)) | |
830 | { | |
831 | gphi *phi = iter.phi (); | |
5ea1ce43 | 832 | tree result = gimple_phi_result (phi); |
f46d3363 AH |
833 | unsigned nargs = gimple_phi_num_args (phi); |
834 | ||
5ea1ce43 AH |
835 | if (!import_p (result)) |
836 | continue; | |
837 | ||
f46d3363 AH |
838 | for (size_t i = 0; i < nargs; ++i) |
839 | if (e_in == gimple_phi_arg_edge (phi, i)) | |
840 | { | |
eb5ee646 | 841 | maybe_register_phi_relation (phi, e_in); |
2f0b6a97 AH |
842 | break; |
843 | } | |
844 | } | |
845 | } | |
8a0fadda | 846 | |
2f0b6a97 | 847 | // Compute outgoing relations from BB to NEXT. |
8a0fadda | 848 | |
2f0b6a97 AH |
849 | void |
850 | path_range_query::compute_outgoing_relations (basic_block bb, basic_block next) | |
851 | { | |
852 | gimple *stmt = last_stmt (bb); | |
f46d3363 | 853 | |
2f0b6a97 AH |
854 | if (stmt |
855 | && gimple_code (stmt) == GIMPLE_COND | |
5ea1ce43 AH |
856 | && (import_p (gimple_cond_lhs (stmt)) |
857 | || import_p (gimple_cond_rhs (stmt)))) | |
2f0b6a97 AH |
858 | { |
859 | int_range<2> r; | |
860 | gcond *cond = as_a<gcond *> (stmt); | |
861 | edge e0 = EDGE_SUCC (bb, 0); | |
862 | edge e1 = EDGE_SUCC (bb, 1); | |
863 | ||
864 | if (e0->dest == next) | |
865 | gcond_edge_range (r, e0); | |
866 | else if (e1->dest == next) | |
867 | gcond_edge_range (r, e1); | |
868 | else | |
869 | gcc_unreachable (); | |
870 | ||
53b3edce | 871 | jt_fur_source src (NULL, this, &m_ranger->gori (), m_path); |
2f0b6a97 | 872 | src.register_outgoing_edges (cond, r, e0, e1); |
f46d3363 AH |
873 | } |
874 | } |