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