]>
Commit | Line | Data |
---|---|---|
90e88fd3 | 1 | /* Code for GIMPLE range related routines. |
aeee4812 | 2 | Copyright (C) 2019-2023 Free Software Foundation, Inc. |
90e88fd3 AM |
3 | Contributed by Andrew MacLeod <amacleod@redhat.com> |
4 | and Aldy Hernandez <aldyh@redhat.com>. | |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 3, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GCC is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GCC; see the file COPYING3. If not see | |
20 | <http://www.gnu.org/licenses/>. */ | |
21 | ||
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "backend.h" | |
90e88fd3 AM |
26 | #include "tree.h" |
27 | #include "gimple.h" | |
28 | #include "ssa.h" | |
29 | #include "gimple-pretty-print.h" | |
30 | #include "gimple-iterator.h" | |
90e88fd3 AM |
31 | #include "tree-cfg.h" |
32 | #include "fold-const.h" | |
33 | #include "tree-cfg.h" | |
90e88fd3 | 34 | #include "cfgloop.h" |
90e88fd3 | 35 | #include "tree-scalar-evolution.h" |
90e88fd3 | 36 | #include "gimple-range.h" |
fc407675 | 37 | #include "gimple-fold.h" |
c6bb1db7 | 38 | #include "gimple-walk.h" |
90e88fd3 | 39 | |
b7501739 | 40 | gimple_ranger::gimple_ranger (bool use_imm_uses) : |
053e1d64 | 41 | non_executable_edge_flag (cfun), |
b7501739 | 42 | m_cache (non_executable_edge_flag, use_imm_uses), |
fc407675 AM |
43 | tracer (""), |
44 | current_bb (NULL) | |
a2c91733 AM |
45 | { |
46 | // If the cache has a relation oracle, use it. | |
47 | m_oracle = m_cache.oracle (); | |
9cb114fd | 48 | if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE)) |
e68c8280 | 49 | tracer.enable_trace (); |
5deacf60 AM |
50 | m_stmt_list.create (0); |
51 | m_stmt_list.safe_grow (num_ssa_names); | |
52 | m_stmt_list.truncate (0); | |
053e1d64 AM |
53 | |
54 | // Ensure the not_executable flag is clear everywhere. | |
55 | if (flag_checking) | |
56 | { | |
57 | basic_block bb; | |
58 | FOR_ALL_BB_FN (bb, cfun) | |
59 | { | |
60 | edge_iterator ei; | |
61 | edge e; | |
62 | FOR_EACH_EDGE (e, ei, bb->succs) | |
63 | gcc_checking_assert ((e->flags & non_executable_edge_flag) == 0); | |
64 | } | |
65 | } | |
a2c91733 AM |
66 | } |
67 | ||
5deacf60 AM |
68 | gimple_ranger::~gimple_ranger () |
69 | { | |
70 | m_stmt_list.release (); | |
71 | } | |
72 | ||
71baa009 AM |
73 | // Return a range_query which accesses just the known global values. |
74 | ||
75 | range_query & | |
76 | gimple_ranger::const_query () | |
77 | { | |
78 | return m_cache.const_query (); | |
79 | } | |
80 | ||
90e88fd3 | 81 | bool |
45c8523d | 82 | gimple_ranger::range_of_expr (vrange &r, tree expr, gimple *stmt) |
90e88fd3 | 83 | { |
e68c8280 | 84 | unsigned idx; |
90e88fd3 | 85 | if (!gimple_range_ssa_p (expr)) |
caa60c12 | 86 | return get_tree_range (r, expr, stmt); |
90e88fd3 | 87 | |
e68c8280 AM |
88 | if ((idx = tracer.header ("range_of_expr("))) |
89 | { | |
90 | print_generic_expr (dump_file, expr, TDF_SLIM); | |
91 | fputs (")", dump_file); | |
92 | if (stmt) | |
93 | { | |
94 | fputs (" at stmt ", dump_file); | |
95 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
96 | } | |
97 | else | |
98 | fputs ("\n", dump_file); | |
99 | } | |
100 | ||
90e88fd3 AM |
101 | // If there is no statement, just get the global value. |
102 | if (!stmt) | |
103 | { | |
45c8523d | 104 | Value_Range tmp (TREE_TYPE (expr)); |
d986ff50 | 105 | m_cache.get_global_range (r, expr); |
fc407675 | 106 | // Pick up implied context information from the on-entry cache |
0cd653bd AM |
107 | // if current_bb is set. Do not attempt any new calculations. |
108 | if (current_bb && m_cache.block_range (tmp, current_bb, expr, false)) | |
fc407675 AM |
109 | { |
110 | r.intersect (tmp); | |
111 | char str[80]; | |
112 | sprintf (str, "picked up range from bb %d\n",current_bb->index); | |
113 | if (idx) | |
114 | tracer.print (idx, str); | |
115 | } | |
90e88fd3 | 116 | } |
715914d3 AM |
117 | // For a debug stmt, pick the best value currently available, do not |
118 | // trigger new value calculations. PR 100781. | |
e68c8280 AM |
119 | else if (is_gimple_debug (stmt)) |
120 | m_cache.range_of_expr (r, expr, stmt); | |
121 | else | |
715914d3 | 122 | { |
e68c8280 AM |
123 | basic_block bb = gimple_bb (stmt); |
124 | gimple *def_stmt = SSA_NAME_DEF_STMT (expr); | |
90e88fd3 | 125 | |
e68c8280 AM |
126 | // If name is defined in this block, try to get an range from S. |
127 | if (def_stmt && gimple_bb (def_stmt) == bb) | |
128 | { | |
761cc32e | 129 | // Declared in this block, if it has a global set, check for an |
b7501739 AM |
130 | // override from a block walk, otherwise calculate it. |
131 | if (m_cache.get_global_range (r, expr)) | |
132 | m_cache.block_range (r, bb, expr, false); | |
133 | else | |
c6bb1db7 | 134 | range_of_stmt (r, def_stmt, expr); |
e68c8280 AM |
135 | } |
136 | // Otherwise OP comes from outside this block, use range on entry. | |
137 | else | |
138 | range_on_entry (r, bb, expr); | |
35c78c6f | 139 | } |
e68c8280 AM |
140 | if (idx) |
141 | tracer.trailer (idx, "range_of_expr", true, expr, r); | |
90e88fd3 AM |
142 | return true; |
143 | } | |
144 | ||
145 | // Return the range of NAME on entry to block BB in R. | |
146 | ||
147 | void | |
45c8523d | 148 | gimple_ranger::range_on_entry (vrange &r, basic_block bb, tree name) |
90e88fd3 | 149 | { |
45c8523d | 150 | Value_Range entry_range (TREE_TYPE (name)); |
90e88fd3 AM |
151 | gcc_checking_assert (gimple_range_ssa_p (name)); |
152 | ||
e68c8280 AM |
153 | unsigned idx; |
154 | if ((idx = tracer.header ("range_on_entry ("))) | |
155 | { | |
156 | print_generic_expr (dump_file, name, TDF_SLIM); | |
157 | fprintf (dump_file, ") to BB %d\n", bb->index); | |
158 | } | |
159 | ||
90e88fd3 | 160 | // Start with any known range |
c25d317c | 161 | range_of_stmt (r, SSA_NAME_DEF_STMT (name), name); |
90e88fd3 AM |
162 | |
163 | // Now see if there is any on_entry value which may refine it. | |
164 | if (m_cache.block_range (entry_range, bb, name)) | |
165 | r.intersect (entry_range); | |
35c78c6f | 166 | |
e68c8280 AM |
167 | if (idx) |
168 | tracer.trailer (idx, "range_on_entry", true, name, r); | |
90e88fd3 AM |
169 | } |
170 | ||
171 | // Calculate the range for NAME at the end of block BB and return it in R. | |
172 | // Return false if no range can be calculated. | |
173 | ||
174 | void | |
45c8523d | 175 | gimple_ranger::range_on_exit (vrange &r, basic_block bb, tree name) |
90e88fd3 AM |
176 | { |
177 | // on-exit from the exit block? | |
c25d317c | 178 | gcc_checking_assert (gimple_range_ssa_p (name)); |
90e88fd3 | 179 | |
e68c8280 AM |
180 | unsigned idx; |
181 | if ((idx = tracer.header ("range_on_exit ("))) | |
182 | { | |
183 | print_generic_expr (dump_file, name, TDF_SLIM); | |
184 | fprintf (dump_file, ") from BB %d\n", bb->index); | |
185 | } | |
186 | ||
d942d733 AM |
187 | gimple *s = SSA_NAME_DEF_STMT (name); |
188 | basic_block def_bb = gimple_bb (s); | |
189 | // If this is not the definition block, get the range on the last stmt in | |
190 | // the block... if there is one. | |
191 | if (def_bb != bb) | |
fe8ac82f | 192 | s = last_nondebug_stmt (bb); |
d942d733 AM |
193 | // If there is no statement provided, get the range_on_entry for this block. |
194 | if (s) | |
c25d317c | 195 | range_of_expr (r, name, s); |
d942d733 | 196 | else |
35c78c6f | 197 | range_on_entry (r, bb, name); |
90e88fd3 | 198 | gcc_checking_assert (r.undefined_p () |
6e02de94 | 199 | || range_compatible_p (r.type (), TREE_TYPE (name))); |
e68c8280 AM |
200 | |
201 | if (idx) | |
202 | tracer.trailer (idx, "range_on_exit", true, name, r); | |
90e88fd3 AM |
203 | } |
204 | ||
205 | // Calculate a range for NAME on edge E and return it in R. | |
206 | ||
207 | bool | |
45c8523d | 208 | gimple_ranger::range_on_edge (vrange &r, edge e, tree name) |
90e88fd3 | 209 | { |
45c8523d | 210 | Value_Range edge_range (TREE_TYPE (name)); |
ca1e4b26 AH |
211 | |
212 | if (!r.supports_type_p (TREE_TYPE (name))) | |
213 | return false; | |
90e88fd3 | 214 | |
4d92a69f AM |
215 | // Do not process values along abnormal edges. |
216 | if (e->flags & EDGE_ABNORMAL) | |
217 | return get_tree_range (r, name, NULL); | |
93ac832f | 218 | |
e68c8280 AM |
219 | unsigned idx; |
220 | if ((idx = tracer.header ("range_on_edge ("))) | |
221 | { | |
222 | print_generic_expr (dump_file, name, TDF_SLIM); | |
223 | fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index); | |
224 | } | |
225 | ||
73cf73af | 226 | // Check to see if the edge is executable. |
053e1d64 | 227 | if ((e->flags & non_executable_edge_flag)) |
73cf73af AM |
228 | { |
229 | r.set_undefined (); | |
230 | if (idx) | |
231 | tracer.trailer (idx, "range_on_edge [Unexecutable] ", true, | |
232 | name, r); | |
233 | return true; | |
234 | } | |
90e88fd3 | 235 | |
73cf73af AM |
236 | bool res = true; |
237 | if (!gimple_range_ssa_p (name)) | |
a031bb7a | 238 | res = get_tree_range (r, name, NULL); |
73cf73af AM |
239 | else |
240 | { | |
241 | range_on_exit (r, e->src, name); | |
c6bb1db7 AM |
242 | // If this is not an abnormal edge, check for a non-null exit . |
243 | if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0) | |
b7501739 | 244 | m_cache.m_exit.maybe_adjust_range (r, name, e->src); |
73cf73af AM |
245 | gcc_checking_assert (r.undefined_p () |
246 | || range_compatible_p (r.type(), TREE_TYPE (name))); | |
247 | ||
248 | // Check to see if NAME is defined on edge e. | |
249 | if (m_cache.range_on_edge (edge_range, e, name)) | |
250 | r.intersect (edge_range); | |
251 | } | |
90e88fd3 | 252 | |
e68c8280 | 253 | if (idx) |
73cf73af | 254 | tracer.trailer (idx, "range_on_edge", res, name, r); |
a031bb7a | 255 | return res; |
90e88fd3 AM |
256 | } |
257 | ||
dc6758f0 AM |
258 | // fold_range wrapper for range_of_stmt to use as an internal client. |
259 | ||
260 | bool | |
45c8523d | 261 | gimple_ranger::fold_range_internal (vrange &r, gimple *s, tree name) |
dc6758f0 AM |
262 | { |
263 | fold_using_range f; | |
87f9ac93 | 264 | fur_depend src (s, &(gori ()), this); |
dc6758f0 AM |
265 | return f.fold_stmt (r, s, src, name); |
266 | } | |
267 | ||
90e88fd3 AM |
268 | // Calculate a range for statement S and return it in R. If NAME is |
269 | // provided it represents the SSA_NAME on the LHS of the statement. | |
270 | // It is only required if there is more than one lhs/output. Check | |
271 | // the global cache for NAME first to see if the evaluation can be | |
c25d317c | 272 | // avoided. If a range cannot be calculated, return false and UNDEFINED. |
90e88fd3 AM |
273 | |
274 | bool | |
45c8523d | 275 | gimple_ranger::range_of_stmt (vrange &r, gimple *s, tree name) |
90e88fd3 | 276 | { |
e68c8280 | 277 | bool res; |
c25d317c AM |
278 | r.set_undefined (); |
279 | ||
e68c8280 AM |
280 | unsigned idx; |
281 | if ((idx = tracer.header ("range_of_stmt ("))) | |
282 | { | |
283 | if (name) | |
284 | print_generic_expr (dump_file, name, TDF_SLIM); | |
285 | fputs (") at stmt ", dump_file); | |
286 | print_gimple_stmt (dump_file, s, 0, TDF_SLIM); | |
287 | } | |
288 | ||
90e88fd3 AM |
289 | if (!name) |
290 | name = gimple_get_lhs (s); | |
291 | ||
c25d317c | 292 | // If no name, simply call the base routine. |
90e88fd3 | 293 | if (!name) |
cb596fd4 AM |
294 | { |
295 | res = fold_range_internal (r, s, NULL_TREE); | |
296 | if (res && is_a <gcond *> (s)) | |
297 | { | |
298 | // Update any exports in the cache if this is a gimple cond statement. | |
299 | tree exp; | |
300 | basic_block bb = gimple_bb (s); | |
301 | FOR_EACH_GORI_EXPORT_NAME (m_cache.m_gori, bb, exp) | |
302 | m_cache.propagate_updated_value (exp, bb); | |
303 | } | |
304 | } | |
e68c8280 | 305 | else if (!gimple_range_ssa_p (name)) |
4d92a69f | 306 | res = get_tree_range (r, name, NULL); |
e68c8280 AM |
307 | else |
308 | { | |
d986ff50 | 309 | bool current; |
5deacf60 | 310 | // Check if the stmt has already been processed. |
d986ff50 AM |
311 | if (m_cache.get_global_range (r, name, current)) |
312 | { | |
5deacf60 | 313 | // If it isn't stale, use this cached value. |
d986ff50 AM |
314 | if (current) |
315 | { | |
316 | if (idx) | |
317 | tracer.trailer (idx, " cached", true, name, r); | |
318 | return true; | |
319 | } | |
320 | } | |
5deacf60 AM |
321 | else |
322 | prefill_stmt_dependencies (name); | |
323 | ||
324 | // Calculate a new value. | |
45c8523d | 325 | Value_Range tmp (TREE_TYPE (name)); |
e68c8280 AM |
326 | fold_range_internal (tmp, s, name); |
327 | ||
328 | // Combine the new value with the old value. This is required because | |
329 | // the way value propagation works, when the IL changes on the fly we | |
330 | // can sometimes get different results. See PR 97741. | |
257c2be7 AM |
331 | bool changed = r.intersect (tmp); |
332 | m_cache.set_global_range (name, r, changed); | |
e68c8280 AM |
333 | res = true; |
334 | } | |
2dd1f944 | 335 | |
e68c8280 AM |
336 | if (idx) |
337 | tracer.trailer (idx, "range_of_stmt", res, name, r); | |
338 | return res; | |
90e88fd3 AM |
339 | } |
340 | ||
5deacf60 AM |
341 | |
342 | // Check if NAME is a dependency that needs resolving, and push it on the | |
343 | // stack if so. R is a scratch range. | |
344 | ||
345 | inline void | |
45c8523d | 346 | gimple_ranger::prefill_name (vrange &r, tree name) |
5deacf60 AM |
347 | { |
348 | if (!gimple_range_ssa_p (name)) | |
349 | return; | |
350 | gimple *stmt = SSA_NAME_DEF_STMT (name); | |
51ce0638 | 351 | if (!gimple_range_op_handler::supported_p (stmt) && !is_a<gphi *> (stmt)) |
5deacf60 AM |
352 | return; |
353 | ||
354 | bool current; | |
355 | // If this op has not been processed yet, then push it on the stack | |
356 | if (!m_cache.get_global_range (r, name, current)) | |
357 | m_stmt_list.safe_push (name); | |
358 | } | |
359 | ||
c46b5b0a | 360 | // This routine will seed the global cache with most of the dependencies of |
5deacf60 AM |
361 | // NAME. This prevents excessive call depth through the normal API. |
362 | ||
363 | void | |
364 | gimple_ranger::prefill_stmt_dependencies (tree ssa) | |
365 | { | |
366 | if (SSA_NAME_IS_DEFAULT_DEF (ssa)) | |
367 | return; | |
368 | ||
5deacf60 AM |
369 | unsigned idx; |
370 | gimple *stmt = SSA_NAME_DEF_STMT (ssa); | |
371 | gcc_checking_assert (stmt && gimple_bb (stmt)); | |
372 | ||
cb137e85 | 373 | // Only pre-process range-ops and phis. |
51ce0638 | 374 | if (!gimple_range_op_handler::supported_p (stmt) && !is_a<gphi *> (stmt)) |
5deacf60 AM |
375 | return; |
376 | ||
377 | // Mark where on the stack we are starting. | |
378 | unsigned start = m_stmt_list.length (); | |
379 | m_stmt_list.safe_push (ssa); | |
380 | ||
381 | idx = tracer.header ("ROS dependence fill\n"); | |
382 | ||
383 | // Loop until back at the start point. | |
384 | while (m_stmt_list.length () > start) | |
385 | { | |
386 | tree name = m_stmt_list.last (); | |
387 | // NULL is a marker which indicates the next name in the stack has now | |
388 | // been fully resolved, so we can fold it. | |
389 | if (!name) | |
390 | { | |
391 | // Pop the NULL, then pop the name. | |
392 | m_stmt_list.pop (); | |
393 | name = m_stmt_list.pop (); | |
394 | // Don't fold initial request, it will be calculated upon return. | |
395 | if (m_stmt_list.length () > start) | |
396 | { | |
397 | // Fold and save the value for NAME. | |
398 | stmt = SSA_NAME_DEF_STMT (name); | |
45c8523d | 399 | Value_Range r (TREE_TYPE (name)); |
5deacf60 | 400 | fold_range_internal (r, stmt, name); |
362e2a9c | 401 | // Make sure we don't lose any current global info. |
45c8523d | 402 | Value_Range tmp (TREE_TYPE (name)); |
362e2a9c | 403 | m_cache.get_global_range (tmp, name); |
257c2be7 AM |
404 | bool changed = tmp.intersect (r); |
405 | m_cache.set_global_range (name, tmp, changed); | |
5deacf60 AM |
406 | } |
407 | continue; | |
408 | } | |
409 | ||
410 | // Add marker indicating previous NAME in list should be folded | |
411 | // when we get to this NULL. | |
412 | m_stmt_list.safe_push (NULL_TREE); | |
413 | stmt = SSA_NAME_DEF_STMT (name); | |
414 | ||
415 | if (idx) | |
416 | { | |
417 | tracer.print (idx, "ROS dep fill ("); | |
418 | print_generic_expr (dump_file, name, TDF_SLIM); | |
419 | fputs (") at stmt ", dump_file); | |
420 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
421 | } | |
422 | ||
cb137e85 AM |
423 | gphi *phi = dyn_cast <gphi *> (stmt); |
424 | if (phi) | |
425 | { | |
45c8523d | 426 | Value_Range r (TREE_TYPE (gimple_phi_result (phi))); |
cb137e85 AM |
427 | for (unsigned x = 0; x < gimple_phi_num_args (phi); x++) |
428 | prefill_name (r, gimple_phi_arg_def (phi, x)); | |
429 | } | |
430 | else | |
431 | { | |
51ce0638 | 432 | gimple_range_op_handler handler (stmt); |
0ef9991d | 433 | if (handler) |
ce8dbe7d | 434 | { |
0ef9991d AM |
435 | tree op = handler.operand2 (); |
436 | if (op) | |
437 | { | |
438 | Value_Range r (TREE_TYPE (op)); | |
439 | prefill_name (r, op); | |
440 | } | |
441 | op = handler.operand1 (); | |
442 | if (op) | |
443 | { | |
444 | Value_Range r (TREE_TYPE (op)); | |
445 | prefill_name (r, op); | |
446 | } | |
ce8dbe7d | 447 | } |
cb137e85 | 448 | } |
5deacf60 AM |
449 | } |
450 | if (idx) | |
45c8523d AH |
451 | { |
452 | unsupported_range r; | |
453 | tracer.trailer (idx, "ROS ", false, ssa, r); | |
454 | } | |
5deacf60 AM |
455 | } |
456 | ||
457 | ||
fc407675 | 458 | // This routine will invoke the gimple fold_stmt routine, providing context to |
c46b5b0a | 459 | // range_of_expr calls via an private internal API. |
fc407675 AM |
460 | |
461 | bool | |
462 | gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree)) | |
463 | { | |
464 | gimple *stmt = gsi_stmt (*gsi); | |
465 | current_bb = gimple_bb (stmt); | |
466 | bool ret = ::fold_stmt (gsi, valueize); | |
467 | current_bb = NULL; | |
468 | return ret; | |
469 | } | |
470 | ||
156d7d8d AM |
471 | // Called during dominator walks to register any inferred ranges that take |
472 | // effect from this point forward. | |
c6bb1db7 AM |
473 | |
474 | void | |
156d7d8d | 475 | gimple_ranger::register_inferred_ranges (gimple *s) |
c6bb1db7 | 476 | { |
af342799 AM |
477 | // First, export the LHS if it is a new global range. |
478 | tree lhs = gimple_get_lhs (s); | |
479 | if (lhs) | |
480 | { | |
0fd3c706 | 481 | Value_Range tmp (TREE_TYPE (lhs)); |
af342799 | 482 | if (range_of_stmt (tmp, s, lhs) && !tmp.varying_p () |
0a7e721a | 483 | && set_range_info (lhs, tmp) && dump_file) |
af342799 | 484 | { |
af342799 AM |
485 | fprintf (dump_file, "Global Exported: "); |
486 | print_generic_expr (dump_file, lhs, TDF_SLIM); | |
487 | fprintf (dump_file, " = "); | |
0a7e721a | 488 | tmp.dump (dump_file); |
af342799 AM |
489 | fputc ('\n', dump_file); |
490 | } | |
491 | } | |
156d7d8d | 492 | m_cache.apply_inferred_ranges (s); |
c6bb1db7 AM |
493 | } |
494 | ||
c8381199 AM |
495 | // This function will walk the statements in BB to determine if any |
496 | // discovered inferred ranges in the block have any transitive effects, | |
497 | // and if so, register those effects in BB. | |
498 | ||
499 | void | |
500 | gimple_ranger::register_transitive_inferred_ranges (basic_block bb) | |
501 | { | |
502 | // Return if there are no inferred ranges in BB. | |
503 | infer_range_manager &infer = m_cache.m_exit; | |
504 | if (!infer.has_range_p (bb)) | |
505 | return; | |
506 | ||
507 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
508 | fprintf (dump_file, "Checking for transitive inferred ranges in BB %d\n", | |
509 | bb->index); | |
510 | ||
511 | for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si); | |
512 | gsi_next (&si)) | |
513 | { | |
514 | gimple *s = gsi_stmt (si); | |
515 | tree lhs = gimple_get_lhs (s); | |
c46b5b0a | 516 | // If the LHS already has an inferred effect, leave it be. |
c8381199 AM |
517 | if (!gimple_range_ssa_p (lhs) || infer.has_range_p (lhs, bb)) |
518 | continue; | |
519 | // Pick up global value. | |
520 | Value_Range g (TREE_TYPE (lhs)); | |
521 | range_of_expr (g, lhs); | |
522 | ||
523 | // If either dependency has an inferred range, check if recalculating | |
524 | // the LHS is different than the global value. If so, register it as | |
525 | // an inferred range as well. | |
526 | Value_Range r (TREE_TYPE (lhs)); | |
527 | r.set_undefined (); | |
528 | tree name1 = gori ().depend1 (lhs); | |
529 | tree name2 = gori ().depend2 (lhs); | |
530 | if ((name1 && infer.has_range_p (name1, bb)) | |
531 | || (name2 && infer.has_range_p (name2, bb))) | |
532 | { | |
533 | // Check if folding S produces a different result. | |
534 | if (fold_range (r, s, this) && g != r) | |
535 | { | |
536 | infer.add_range (lhs, bb, r); | |
537 | m_cache.register_inferred_value (r, lhs, bb); | |
538 | } | |
539 | } | |
540 | } | |
541 | } | |
542 | ||
6fd485d1 AM |
543 | // When a statement S has changed since the result was cached, re-evaluate |
544 | // and update the global cache. | |
545 | ||
546 | void | |
547 | gimple_ranger::update_stmt (gimple *s) | |
548 | { | |
549 | tree lhs = gimple_get_lhs (s); | |
550 | if (!lhs || !gimple_range_ssa_p (lhs)) | |
551 | return; | |
552 | Value_Range r (TREE_TYPE (lhs)); | |
553 | // Only update if it already had a value. | |
554 | if (m_cache.get_global_range (r, lhs)) | |
555 | { | |
556 | // Re-calculate a new value using just cache values. | |
557 | Value_Range tmp (TREE_TYPE (lhs)); | |
558 | fold_using_range f; | |
0a7b437c | 559 | fur_stmt src (s, &m_cache); |
6fd485d1 AM |
560 | f.fold_stmt (tmp, s, src, lhs); |
561 | ||
562 | // Combine the new value with the old value to check for a change. | |
563 | if (r.intersect (tmp)) | |
564 | { | |
565 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
566 | { | |
567 | print_generic_expr (dump_file, lhs, TDF_SLIM); | |
568 | fprintf (dump_file, " : global value re-evaluated to "); | |
569 | r.dump (dump_file); | |
570 | fputc ('\n', dump_file); | |
571 | } | |
572 | m_cache.set_global_range (lhs, r); | |
573 | } | |
574 | } | |
575 | } | |
576 | ||
90e88fd3 | 577 | // This routine will export whatever global ranges are known to GCC |
160fe603 | 578 | // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields. |
90e88fd3 AM |
579 | |
580 | void | |
581 | gimple_ranger::export_global_ranges () | |
582 | { | |
ed3de423 MS |
583 | /* Cleared after the table header has been printed. */ |
584 | bool print_header = true; | |
585 | for (unsigned x = 1; x < num_ssa_names; x++) | |
90e88fd3 AM |
586 | { |
587 | tree name = ssa_name (x); | |
45c8523d AH |
588 | if (!name) |
589 | continue; | |
590 | Value_Range r (TREE_TYPE (name)); | |
90e88fd3 AM |
591 | if (name && !SSA_NAME_IN_FREE_LIST (name) |
592 | && gimple_range_ssa_p (name) | |
220929c0 | 593 | && m_cache.get_global_range (r, name) |
90e88fd3 AM |
594 | && !r.varying_p()) |
595 | { | |
0a7e721a | 596 | bool updated = set_range_info (name, r); |
17d26698 | 597 | if (!updated || !dump_file) |
ed3de423 MS |
598 | continue; |
599 | ||
600 | if (print_header) | |
601 | { | |
602 | /* Print the header only when there's something else | |
603 | to print below. */ | |
604 | fprintf (dump_file, "Exported global range table:\n"); | |
605 | fprintf (dump_file, "============================\n"); | |
606 | print_header = false; | |
607 | } | |
160fe603 | 608 | |
ed3de423 MS |
609 | print_generic_expr (dump_file, name , TDF_SLIM); |
610 | fprintf (dump_file, " : "); | |
0a7e721a | 611 | r.dump (dump_file); |
ed3de423 | 612 | fprintf (dump_file, "\n"); |
90e88fd3 AM |
613 | } |
614 | } | |
615 | } | |
616 | ||
617 | // Print the known table values to file F. | |
618 | ||
619 | void | |
35c78c6f | 620 | gimple_ranger::dump_bb (FILE *f, basic_block bb) |
90e88fd3 | 621 | { |
35c78c6f AM |
622 | unsigned x; |
623 | edge_iterator ei; | |
624 | edge e; | |
35c78c6f | 625 | fprintf (f, "\n=========== BB %d ============\n", bb->index); |
47ea02bb | 626 | m_cache.dump_bb (f, bb); |
90e88fd3 | 627 | |
35c78c6f | 628 | ::dump_bb (f, bb, 4, TDF_NONE); |
90e88fd3 | 629 | |
35c78c6f AM |
630 | // Now find any globals defined in this block. |
631 | for (x = 1; x < num_ssa_names; x++) | |
632 | { | |
633 | tree name = ssa_name (x); | |
45c8523d AH |
634 | if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name)) |
635 | continue; | |
636 | Value_Range range (TREE_TYPE (name)); | |
637 | if (gimple_bb (SSA_NAME_DEF_STMT (name)) == bb | |
638 | && m_cache.get_global_range (range, name)) | |
90e88fd3 | 639 | { |
35c78c6f | 640 | if (!range.varying_p ()) |
90e88fd3 | 641 | { |
35c78c6f AM |
642 | print_generic_expr (f, name, TDF_SLIM); |
643 | fprintf (f, " : "); | |
644 | range.dump (f); | |
645 | fprintf (f, "\n"); | |
90e88fd3 | 646 | } |
35c78c6f | 647 | |
90e88fd3 | 648 | } |
35c78c6f | 649 | } |
90e88fd3 | 650 | |
35c78c6f AM |
651 | // And now outgoing edges, if they define anything. |
652 | FOR_EACH_EDGE (e, ei, bb->succs) | |
653 | { | |
654 | for (x = 1; x < num_ssa_names; x++) | |
90e88fd3 | 655 | { |
35c78c6f | 656 | tree name = gimple_range_ssa_p (ssa_name (x)); |
45c8523d AH |
657 | if (!name || !gori ().has_edge_range_p (name, e)) |
658 | continue; | |
659 | ||
660 | Value_Range range (TREE_TYPE (name)); | |
661 | if (m_cache.range_on_edge (range, e, name)) | |
90e88fd3 | 662 | { |
35c78c6f | 663 | gimple *s = SSA_NAME_DEF_STMT (name); |
45c8523d | 664 | Value_Range tmp_range (TREE_TYPE (name)); |
35c78c6f AM |
665 | // Only print the range if this is the def block, or |
666 | // the on entry cache for either end of the edge is | |
667 | // set. | |
668 | if ((s && bb == gimple_bb (s)) || | |
e68c8280 AM |
669 | m_cache.block_range (tmp_range, bb, name, false) || |
670 | m_cache.block_range (tmp_range, e->dest, name, false)) | |
90e88fd3 | 671 | { |
35c78c6f | 672 | if (!range.varying_p ()) |
90e88fd3 | 673 | { |
35c78c6f AM |
674 | fprintf (f, "%d->%d ", e->src->index, |
675 | e->dest->index); | |
676 | char c = ' '; | |
677 | if (e->flags & EDGE_TRUE_VALUE) | |
678 | fprintf (f, " (T)%c", c); | |
679 | else if (e->flags & EDGE_FALSE_VALUE) | |
680 | fprintf (f, " (F)%c", c); | |
681 | else | |
682 | fprintf (f, " "); | |
683 | print_generic_expr (f, name, TDF_SLIM); | |
684 | fprintf(f, " : \t"); | |
685 | range.dump(f); | |
686 | fprintf (f, "\n"); | |
90e88fd3 AM |
687 | } |
688 | } | |
689 | } | |
690 | } | |
691 | } | |
35c78c6f AM |
692 | } |
693 | ||
694 | // Print the known table values to file F. | |
695 | ||
696 | void | |
697 | gimple_ranger::dump (FILE *f) | |
698 | { | |
699 | basic_block bb; | |
700 | ||
701 | FOR_EACH_BB_FN (bb, cfun) | |
702 | dump_bb (f, bb); | |
90e88fd3 | 703 | |
47ea02bb | 704 | m_cache.dump (f); |
90e88fd3 AM |
705 | } |
706 | ||
257fd033 AH |
707 | void |
708 | gimple_ranger::debug () | |
709 | { | |
710 | dump (stderr); | |
711 | } | |
712 | ||
77bf9f83 MS |
713 | /* Create a new ranger instance and associate it with function FUN. |
714 | Each call must be paired with a call to disable_ranger to release | |
715 | resources. */ | |
716 | ||
586d6f7a | 717 | gimple_ranger * |
b7501739 | 718 | enable_ranger (struct function *fun, bool use_imm_uses) |
586d6f7a AH |
719 | { |
720 | gimple_ranger *r; | |
721 | ||
56af35de | 722 | gcc_checking_assert (!fun->x_range_query); |
b7501739 | 723 | r = new gimple_ranger (use_imm_uses); |
586d6f7a AH |
724 | fun->x_range_query = r; |
725 | ||
726 | return r; | |
727 | } | |
728 | ||
77bf9f83 MS |
729 | /* Destroy and release the ranger instance associated with function FUN |
730 | and replace it the global ranger. */ | |
731 | ||
586d6f7a AH |
732 | void |
733 | disable_ranger (struct function *fun) | |
734 | { | |
56af35de | 735 | gcc_checking_assert (fun->x_range_query); |
586d6f7a | 736 | delete fun->x_range_query; |
56af35de | 737 | fun->x_range_query = NULL; |
586d6f7a | 738 | } |
53e6d7a3 AM |
739 | |
740 | // ------------------------------------------------------------------------ | |
741 | ||
742 | // If there is a non-varying value associated with NAME, return true and the | |
743 | // range in R. | |
744 | ||
745 | bool | |
746 | assume_query::assume_range_p (vrange &r, tree name) | |
747 | { | |
8a3590e5 | 748 | if (global.get_range (r, name)) |
53e6d7a3 AM |
749 | return !r.varying_p (); |
750 | return false; | |
751 | } | |
752 | ||
753 | // Query used by GORI to pick up any known value on entry to a block. | |
754 | ||
755 | bool | |
756 | assume_query::range_of_expr (vrange &r, tree expr, gimple *stmt) | |
757 | { | |
758 | if (!gimple_range_ssa_p (expr)) | |
759 | return get_tree_range (r, expr, stmt); | |
760 | ||
8a3590e5 | 761 | if (!global.get_range (r, expr)) |
53e6d7a3 AM |
762 | r.set_varying (TREE_TYPE (expr)); |
763 | return true; | |
764 | } | |
765 | ||
766 | // If the current function returns an integral value, and has a single return | |
c46b5b0a | 767 | // statement, it will calculate any SSA_NAMES it can determine ranges for |
53e6d7a3 AM |
768 | // assuming the function returns 1. |
769 | ||
770 | assume_query::assume_query () | |
771 | { | |
772 | basic_block exit_bb = EXIT_BLOCK_PTR_FOR_FN (cfun); | |
773 | if (single_pred_p (exit_bb)) | |
774 | { | |
775 | basic_block bb = single_pred (exit_bb); | |
776 | gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb); | |
777 | if (gsi_end_p (gsi)) | |
778 | return; | |
779 | gimple *s = gsi_stmt (gsi); | |
780 | if (!is_a<greturn *> (s)) | |
781 | return; | |
782 | greturn *gret = as_a<greturn *> (s); | |
783 | tree op = gimple_return_retval (gret); | |
784 | if (!gimple_range_ssa_p (op)) | |
785 | return; | |
786 | tree lhs_type = TREE_TYPE (op); | |
787 | if (!irange::supports_p (lhs_type)) | |
788 | return; | |
789 | ||
790 | unsigned prec = TYPE_PRECISION (lhs_type); | |
791 | int_range<2> lhs_range (lhs_type, wi::one (prec), wi::one (prec)); | |
8a3590e5 | 792 | global.set_range (op, lhs_range); |
53e6d7a3 AM |
793 | |
794 | gimple *def = SSA_NAME_DEF_STMT (op); | |
795 | if (!def || gimple_get_lhs (def) != op) | |
796 | return; | |
797 | fur_stmt src (gret, this); | |
798 | calculate_stmt (def, lhs_range, src); | |
799 | } | |
800 | } | |
801 | ||
802 | // Evaluate operand OP on statement S, using the provided LHS range. | |
803 | // If successful, set the range in the global table, then visit OP's def stmt. | |
804 | ||
805 | void | |
806 | assume_query::calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src) | |
807 | { | |
808 | Value_Range op_range (TREE_TYPE (op)); | |
809 | if (m_gori.compute_operand_range (op_range, s, lhs, op, src) | |
810 | && !op_range.varying_p ()) | |
811 | { | |
812 | Value_Range range (TREE_TYPE (op)); | |
8a3590e5 | 813 | if (global.get_range (range, op)) |
53e6d7a3 | 814 | op_range.intersect (range); |
8a3590e5 | 815 | global.set_range (op, op_range); |
53e6d7a3 AM |
816 | gimple *def_stmt = SSA_NAME_DEF_STMT (op); |
817 | if (def_stmt && gimple_get_lhs (def_stmt) == op) | |
818 | calculate_stmt (def_stmt, op_range, src); | |
819 | } | |
820 | } | |
821 | ||
822 | // Evaluate PHI statement, using the provided LHS range. | |
823 | // Check each constant argument predecessor if it can be taken | |
c46b5b0a | 824 | // provide LHS to any symbolic arguments, and process their def statements. |
53e6d7a3 AM |
825 | |
826 | void | |
827 | assume_query::calculate_phi (gphi *phi, vrange &lhs_range, fur_source &src) | |
828 | { | |
829 | for (unsigned x= 0; x < gimple_phi_num_args (phi); x++) | |
830 | { | |
831 | tree arg = gimple_phi_arg_def (phi, x); | |
832 | Value_Range arg_range (TREE_TYPE (arg)); | |
833 | if (gimple_range_ssa_p (arg)) | |
834 | { | |
835 | // A symbol arg will be the LHS value. | |
836 | arg_range = lhs_range; | |
837 | range_cast (arg_range, TREE_TYPE (arg)); | |
8a3590e5 | 838 | if (!global.get_range (arg_range, arg)) |
53e6d7a3 | 839 | { |
8a3590e5 | 840 | global.set_range (arg, arg_range); |
53e6d7a3 AM |
841 | gimple *def_stmt = SSA_NAME_DEF_STMT (arg); |
842 | if (def_stmt && gimple_get_lhs (def_stmt) == arg) | |
843 | calculate_stmt (def_stmt, arg_range, src); | |
844 | } | |
845 | } | |
846 | else if (get_tree_range (arg_range, arg, NULL)) | |
847 | { | |
848 | // If this is a constant value that differs from LHS, this | |
849 | // edge cannot be taken. | |
850 | arg_range.intersect (lhs_range); | |
851 | if (arg_range.undefined_p ()) | |
852 | continue; | |
853 | // Otherwise check the condition feeding this edge. | |
854 | edge e = gimple_phi_arg_edge (phi, x); | |
855 | check_taken_edge (e, src); | |
856 | } | |
857 | } | |
858 | } | |
859 | ||
860 | // If an edge is known to be taken, examine the outgoing edge to see | |
861 | // if it carries any range information that can also be evaluated. | |
862 | ||
863 | void | |
864 | assume_query::check_taken_edge (edge e, fur_source &src) | |
865 | { | |
866 | gimple *stmt = gimple_outgoing_range_stmt_p (e->src); | |
867 | if (stmt && is_a<gcond *> (stmt)) | |
868 | { | |
869 | int_range<2> cond; | |
870 | gcond_edge_range (cond, e); | |
871 | calculate_stmt (stmt, cond, src); | |
872 | } | |
873 | } | |
874 | ||
875 | // Evaluate statement S which produces range LHS_RANGE. | |
876 | ||
877 | void | |
878 | assume_query::calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src) | |
879 | { | |
880 | gimple_range_op_handler handler (s); | |
881 | if (handler) | |
882 | { | |
883 | tree op = gimple_range_ssa_p (handler.operand1 ()); | |
884 | if (op) | |
885 | calculate_op (op, s, lhs_range, src); | |
886 | op = gimple_range_ssa_p (handler.operand2 ()); | |
887 | if (op) | |
888 | calculate_op (op, s, lhs_range, src); | |
889 | } | |
890 | else if (is_a<gphi *> (s)) | |
891 | { | |
892 | calculate_phi (as_a<gphi *> (s), lhs_range, src); | |
893 | // Don't further check predecessors of blocks with PHIs. | |
894 | return; | |
895 | } | |
896 | ||
897 | // Even if the walk back terminates before the top, if this is a single | |
898 | // predecessor block, see if the predecessor provided any ranges to get here. | |
899 | if (single_pred_p (gimple_bb (s))) | |
900 | check_taken_edge (single_pred_edge (gimple_bb (s)), src); | |
901 | } | |
902 | ||
903 | // Show everything that was calculated. | |
904 | ||
905 | void | |
906 | assume_query::dump (FILE *f) | |
907 | { | |
908 | fprintf (f, "Assumption details calculated:\n"); | |
909 | for (unsigned i = 0; i < num_ssa_names; i++) | |
910 | { | |
911 | tree name = ssa_name (i); | |
912 | if (!name || !gimple_range_ssa_p (name)) | |
913 | continue; | |
914 | tree type = TREE_TYPE (name); | |
915 | if (!Value_Range::supports_type_p (type)) | |
916 | continue; | |
917 | ||
918 | Value_Range assume_range (type); | |
919 | if (assume_range_p (assume_range, name)) | |
920 | { | |
921 | print_generic_expr (f, name, TDF_SLIM); | |
922 | fprintf (f, " -> "); | |
923 | assume_range.dump (f); | |
924 | fputc ('\n', f); | |
925 | } | |
926 | } | |
927 | fprintf (f, "------------------------------\n"); | |
928 | } |