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