Branch data Line data Source code
1 : : /* Code for GIMPLE range related routines.
2 : : Copyright (C) 2019-2025 Free Software Foundation, Inc.
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"
26 : : #include "tree.h"
27 : : #include "gimple.h"
28 : : #include "ssa.h"
29 : : #include "gimple-pretty-print.h"
30 : : #include "gimple-iterator.h"
31 : : #include "tree-cfg.h"
32 : : #include "fold-const.h"
33 : : #include "tree-cfg.h"
34 : : #include "cfgloop.h"
35 : : #include "tree-scalar-evolution.h"
36 : : #include "gimple-range.h"
37 : : #include "gimple-fold.h"
38 : : #include "gimple-walk.h"
39 : :
40 : 28199083 : gimple_ranger::gimple_ranger (bool use_imm_uses) :
41 : 56398166 : non_executable_edge_flag (cfun),
42 : 28199083 : m_cache (non_executable_edge_flag, use_imm_uses),
43 : 28199083 : tracer (""),
44 : 28199083 : current_bb (NULL)
45 : : {
46 : : // Share the oracle from the cache.
47 : 28199083 : share_query (m_cache);
48 : 28199083 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE))
49 : 0 : tracer.enable_trace ();
50 : 28199083 : m_stmt_list.create (0);
51 : 56398166 : m_stmt_list.safe_grow (num_ssa_names);
52 : 28199083 : m_stmt_list.truncate (0);
53 : :
54 : : // Ensure the not_executable flag is clear everywhere.
55 : 28199083 : if (flag_checking)
56 : : {
57 : 28198693 : basic_block bb;
58 : 344252774 : FOR_ALL_BB_FN (bb, cfun)
59 : : {
60 : 316054081 : edge_iterator ei;
61 : 316054081 : edge e;
62 : 707323236 : FOR_EACH_EDGE (e, ei, bb->succs)
63 : 391269155 : gcc_checking_assert ((e->flags & non_executable_edge_flag) == 0);
64 : : }
65 : : }
66 : 28199083 : }
67 : :
68 : 56397596 : gimple_ranger::~gimple_ranger ()
69 : : {
70 : 28199083 : m_stmt_list.release ();
71 : 56397596 : }
72 : :
73 : : // Return a range_query which accesses just the known global values.
74 : :
75 : : range_query &
76 : 0 : gimple_ranger::const_query ()
77 : : {
78 : 0 : return m_cache.const_query ();
79 : : }
80 : :
81 : : bool
82 : 559534311 : gimple_ranger::range_of_expr (vrange &r, tree expr, gimple *stmt)
83 : : {
84 : 559534311 : unsigned idx;
85 : 559534311 : if (!gimple_range_ssa_p (expr))
86 : 91344076 : return get_tree_range (r, expr, stmt);
87 : :
88 : 468190235 : if ((idx = tracer.header ("range_of_expr(")))
89 : : {
90 : 0 : print_generic_expr (dump_file, expr, TDF_SLIM);
91 : 0 : fputs (")", dump_file);
92 : 0 : if (stmt)
93 : : {
94 : 0 : fputs (" at stmt ", dump_file);
95 : 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
96 : : }
97 : : else
98 : 0 : fputs ("\n", dump_file);
99 : : }
100 : :
101 : : // If there is no statement, just get the global value.
102 : 468190235 : if (!stmt)
103 : : {
104 : 43585872 : value_range tmp (TREE_TYPE (expr));
105 : : // If there is no global range for EXPR yet, try to evaluate it.
106 : : // This call sets R to a global range regardless.
107 : 43585872 : if (!m_cache.get_global_range (r, expr))
108 : : {
109 : 4561807 : gimple *s = SSA_NAME_DEF_STMT (expr);
110 : : // Calculate a range for S if it is safe to do so.
111 : 4561807 : if (s && gimple_bb (s) && gimple_get_lhs (s) == expr)
112 : 4333580 : return range_of_stmt (r, s);
113 : : }
114 : : // Pick up implied context information from the on-entry cache
115 : : // if current_bb is set. Do not attempt any new calculations.
116 : 39252292 : if (current_bb && m_cache.block_range (tmp, current_bb, expr, false))
117 : : {
118 : 1032166 : r.intersect (tmp);
119 : 1032166 : char str[80];
120 : 1032166 : sprintf (str, "picked up range from bb %d\n",current_bb->index);
121 : 1032166 : if (idx)
122 : 0 : tracer.print (idx, str);
123 : : }
124 : 43585872 : }
125 : : // For a debug stmt, pick the best value currently available, do not
126 : : // trigger new value calculations. PR 100781.
127 : 424604363 : else if (is_gimple_debug (stmt))
128 : 39877778 : m_cache.range_of_expr (r, expr, stmt);
129 : : else
130 : : {
131 : 384726585 : basic_block bb = gimple_bb (stmt);
132 : 384726585 : gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
133 : :
134 : : // If name is defined in this block, try to get an range from S.
135 : 384726585 : if (def_stmt && gimple_bb (def_stmt) == bb)
136 : : {
137 : : // Declared in this block, if it has a global set, check for an
138 : : // override from a block walk, otherwise calculate it.
139 : 236877627 : if (m_cache.get_global_range (r, expr))
140 : 200980280 : m_cache.block_range (r, bb, expr, false);
141 : : else
142 : 35897347 : range_of_stmt (r, def_stmt, expr);
143 : : }
144 : : // Otherwise OP comes from outside this block, use range on entry.
145 : : else
146 : 147848958 : range_on_entry (r, bb, expr);
147 : : }
148 : 463856655 : if (idx)
149 : 0 : tracer.trailer (idx, "range_of_expr", true, expr, r);
150 : : return true;
151 : : }
152 : :
153 : : // Return the range of NAME on entry to block BB in R.
154 : :
155 : : bool
156 : 181267687 : gimple_ranger::range_on_entry (vrange &r, basic_block bb, tree name)
157 : : {
158 : 181267687 : if (!gimple_range_ssa_p (name))
159 : 0 : return get_tree_range (r, name, NULL, bb, NULL);
160 : :
161 : 181267687 : value_range entry_range (TREE_TYPE (name));
162 : :
163 : 181267687 : unsigned idx;
164 : 181267687 : if ((idx = tracer.header ("range_on_entry (")))
165 : : {
166 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
167 : 0 : fprintf (dump_file, ") to BB %d\n", bb->index);
168 : : }
169 : :
170 : : // Start with any known range
171 : 181267687 : range_of_stmt (r, SSA_NAME_DEF_STMT (name), name);
172 : :
173 : : // Now see if there is any on_entry value which may refine it.
174 : 181267687 : if (m_cache.block_range (entry_range, bb, name))
175 : 117991748 : r.intersect (entry_range);
176 : :
177 : 181267687 : if (idx)
178 : 0 : tracer.trailer (idx, "range_on_entry", true, name, r);
179 : 181267687 : return true;
180 : 181267687 : }
181 : :
182 : : // Calculate the range for NAME at the end of block BB and return it in R.
183 : : // Return false if no range can be calculated.
184 : :
185 : : bool
186 : 66315581 : gimple_ranger::range_on_exit (vrange &r, basic_block bb, tree name)
187 : : {
188 : 66315581 : if (!gimple_range_ssa_p (name))
189 : 0 : return get_tree_range (r, name, NULL, NULL, bb);
190 : :
191 : 66315581 : unsigned idx;
192 : 66315581 : if ((idx = tracer.header ("range_on_exit (")))
193 : : {
194 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
195 : 0 : fprintf (dump_file, ") from BB %d\n", bb->index);
196 : : }
197 : :
198 : 66315581 : gimple *s = SSA_NAME_DEF_STMT (name);
199 : 66315581 : basic_block def_bb = gimple_bb (s);
200 : : // If this is not the definition block, get the range on the last stmt in
201 : : // the block... if there is one.
202 : 66315581 : if (def_bb != bb)
203 : : {
204 : 30612704 : if (bb->flags & BB_RTL)
205 : : s = NULL;
206 : : else
207 : 30593698 : s = last_nondebug_stmt (bb);
208 : : }
209 : : // If there is no statement provided, get the range_on_entry for this block.
210 : 30593698 : if (s)
211 : 53371220 : range_of_expr (r, name, s);
212 : : else
213 : 12944361 : range_on_entry (r, bb, name);
214 : 66315581 : gcc_checking_assert (r.undefined_p ()
215 : : || range_compatible_p (r.type (), TREE_TYPE (name)));
216 : :
217 : 66315581 : if (idx)
218 : 0 : tracer.trailer (idx, "range_on_exit", true, name, r);
219 : : return true;
220 : : }
221 : :
222 : : // Calculate a range for NAME on edge E and return it in R.
223 : :
224 : : bool
225 : 81343615 : gimple_ranger::range_on_edge (vrange &r, edge e, tree name)
226 : : {
227 : 81343615 : value_range edge_range (TREE_TYPE (name));
228 : :
229 : 81343615 : if (!r.supports_type_p (TREE_TYPE (name)))
230 : : return false;
231 : :
232 : : // Do not process values along abnormal edges.
233 : 81343615 : if (e->flags & EDGE_ABNORMAL)
234 : 77 : return get_tree_range (r, name, NULL);
235 : :
236 : 81343538 : unsigned idx;
237 : 81343538 : if ((idx = tracer.header ("range_on_edge (")))
238 : : {
239 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
240 : 0 : fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index);
241 : : }
242 : :
243 : : // Check to see if the edge is executable.
244 : 81343538 : if ((e->flags & non_executable_edge_flag))
245 : : {
246 : 231737 : r.set_undefined ();
247 : 231737 : if (idx)
248 : 0 : tracer.trailer (idx, "range_on_edge [Unexecutable] ", true,
249 : : name, r);
250 : 231737 : return true;
251 : : }
252 : :
253 : 81111801 : bool res = true;
254 : 81111801 : if (!gimple_range_ssa_p (name))
255 : 14796220 : res = get_tree_range (r, name, NULL, NULL, NULL, e);
256 : : else
257 : : {
258 : 66315581 : range_on_exit (r, e->src, name);
259 : : // If this is not an abnormal edge, check for a non-null exit .
260 : 66315581 : if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
261 : 65934645 : infer_oracle ().maybe_adjust_range (r, name, e->src);
262 : 66315581 : gcc_checking_assert (r.undefined_p ()
263 : : || range_compatible_p (r.type(), TREE_TYPE (name)));
264 : :
265 : : // Check to see if NAME is defined on edge e.
266 : 66315581 : if (m_cache.range_on_edge (edge_range, e, name))
267 : 66315581 : r.intersect (edge_range);
268 : : }
269 : :
270 : 81111801 : if (idx)
271 : 0 : tracer.trailer (idx, "range_on_edge", res, name, r);
272 : : return res;
273 : 81343615 : }
274 : :
275 : : // fold_range wrapper for range_of_stmt to use as an internal client.
276 : :
277 : : bool
278 : 162155017 : gimple_ranger::fold_range_internal (vrange &r, gimple *s, tree name)
279 : : {
280 : 162155017 : fold_using_range f;
281 : 162155017 : fur_depend src (s, this, &m_cache);
282 : 162155017 : return f.fold_stmt (r, s, src, name);
283 : : }
284 : :
285 : : // Calculate a range for statement S and return it in R. If NAME is
286 : : // provided it represents the SSA_NAME on the LHS of the statement.
287 : : // It is only required if there is more than one lhs/output. Check
288 : : // the global cache for NAME first to see if the evaluation can be
289 : : // avoided. If a range cannot be calculated, return false and UNDEFINED.
290 : :
291 : : bool
292 : 378502791 : gimple_ranger::range_of_stmt (vrange &r, gimple *s, tree name)
293 : : {
294 : 378502791 : bool res;
295 : 378502791 : r.set_undefined ();
296 : :
297 : 378502791 : unsigned idx;
298 : 378502791 : if ((idx = tracer.header ("range_of_stmt (")))
299 : : {
300 : 0 : if (name)
301 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
302 : 0 : fputs (") at stmt ", dump_file);
303 : 0 : print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
304 : : }
305 : :
306 : 378502791 : if (!name)
307 : 25715480 : name = gimple_get_lhs (s);
308 : :
309 : : // If no name, simply call the base routine.
310 : 25715480 : if (!name)
311 : : {
312 : 21381900 : res = fold_range_internal (r, s, NULL_TREE);
313 : 21381900 : if (res && is_a <gcond *> (s))
314 : : {
315 : : // Update any exports in the cache if this is a gimple cond statement.
316 : 21336565 : tree exp;
317 : 21336565 : basic_block bb = gimple_bb (s);
318 : 64023178 : FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb, exp)
319 : 42686613 : m_cache.propagate_updated_value (exp, bb);
320 : : }
321 : : }
322 : 357120891 : else if (!gimple_range_ssa_p (name))
323 : 35311614 : res = get_tree_range (r, name, NULL);
324 : : else
325 : : {
326 : 321809277 : bool current;
327 : : // Check if the stmt has already been processed.
328 : 321809277 : if (m_cache.get_global_range (r, name, current))
329 : : {
330 : : // If it isn't stale, use this cached value.
331 : 218158269 : if (current)
332 : : {
333 : 205959776 : if (idx)
334 : 0 : tracer.trailer (idx, " cached", true, name, r);
335 : 205959776 : return true;
336 : : }
337 : : }
338 : : else
339 : 103651008 : prefill_stmt_dependencies (name);
340 : :
341 : : // Calculate a new value.
342 : 115849501 : value_range tmp (TREE_TYPE (name));
343 : 115849501 : fold_range_internal (tmp, s, name);
344 : :
345 : : // Combine the new value with the old value. This is required because
346 : : // the way value propagation works, when the IL changes on the fly we
347 : : // can sometimes get different results. See PR 97741.
348 : 115849501 : bool changed = r.intersect (tmp);
349 : 115849501 : m_cache.set_global_range (name, r, changed);
350 : 115849501 : res = true;
351 : 115849501 : }
352 : :
353 : 172543015 : if (idx)
354 : 0 : tracer.trailer (idx, "range_of_stmt", res, name, r);
355 : : return res;
356 : : }
357 : :
358 : :
359 : : // Check if NAME is a dependency that needs resolving, and push it on the
360 : : // stack if so. R is a scratch range.
361 : :
362 : : inline void
363 : 139311542 : gimple_ranger::prefill_name (vrange &r, tree name)
364 : : {
365 : 139311542 : if (!gimple_range_ssa_p (name))
366 : : return;
367 : 102138217 : gimple *stmt = SSA_NAME_DEF_STMT (name);
368 : 102138217 : if (!gimple_range_op_handler::supported_p (stmt) && !is_a<gphi *> (stmt))
369 : : return;
370 : :
371 : : // If this op has not been processed yet, then push it on the stack
372 : 72688725 : if (!m_cache.get_global_range (r, name))
373 : : {
374 : 24923616 : bool current;
375 : : // Set the global cache value and mark as alway_current.
376 : 24923616 : m_cache.get_global_range (r, name, current);
377 : 24923616 : m_stmt_list.safe_push (name);
378 : : }
379 : : }
380 : :
381 : : // This routine will seed the global cache with most of the dependencies of
382 : : // NAME. This prevents excessive call depth through the normal API.
383 : :
384 : : void
385 : 103651008 : gimple_ranger::prefill_stmt_dependencies (tree ssa)
386 : : {
387 : 103651008 : if (SSA_NAME_IS_DEFAULT_DEF (ssa))
388 : : return;
389 : :
390 : 93367273 : unsigned idx;
391 : 93367273 : gimple *stmt = SSA_NAME_DEF_STMT (ssa);
392 : 93367273 : gcc_checking_assert (stmt && gimple_bb (stmt));
393 : :
394 : : // Only pre-process range-ops and phis.
395 : 93367273 : if (!gimple_range_op_handler::supported_p (stmt) && !is_a<gphi *> (stmt))
396 : : return;
397 : :
398 : : // Mark where on the stack we are starting.
399 : 51569633 : unsigned start = m_stmt_list.length ();
400 : 51569633 : m_stmt_list.safe_push (ssa);
401 : :
402 : 51569633 : idx = tracer.header ("ROS dependence fill\n");
403 : :
404 : : // Loop until back at the start point.
405 : 204556131 : while (m_stmt_list.length () > start)
406 : : {
407 : 152986498 : tree name = m_stmt_list.last ();
408 : : // NULL is a marker which indicates the next name in the stack has now
409 : : // been fully resolved, so we can fold it.
410 : 152986498 : if (!name)
411 : : {
412 : : // Pop the NULL, then pop the name.
413 : 76493249 : m_stmt_list.pop ();
414 : 76493249 : name = m_stmt_list.pop ();
415 : : // Don't fold initial request, it will be calculated upon return.
416 : 76493249 : if (m_stmt_list.length () > start)
417 : : {
418 : : // Fold and save the value for NAME.
419 : 24923616 : stmt = SSA_NAME_DEF_STMT (name);
420 : 24923616 : value_range r (TREE_TYPE (name));
421 : 24923616 : fold_range_internal (r, stmt, name);
422 : : // Make sure we don't lose any current global info.
423 : 24923616 : value_range tmp (TREE_TYPE (name));
424 : 24923616 : m_cache.get_global_range (tmp, name);
425 : 24923616 : bool changed = tmp.intersect (r);
426 : 24923616 : m_cache.set_global_range (name, tmp, changed);
427 : 24923616 : }
428 : 76493249 : continue;
429 : 76493249 : }
430 : :
431 : : // Add marker indicating previous NAME in list should be folded
432 : : // when we get to this NULL.
433 : 76493249 : m_stmt_list.safe_push (NULL_TREE);
434 : 76493249 : stmt = SSA_NAME_DEF_STMT (name);
435 : :
436 : 76493249 : if (idx)
437 : : {
438 : 0 : tracer.print (idx, "ROS dep fill (");
439 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
440 : 0 : fputs (") at stmt ", dump_file);
441 : 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
442 : : }
443 : :
444 : 76493249 : gphi *phi = dyn_cast <gphi *> (stmt);
445 : 76493249 : if (phi)
446 : : {
447 : 19380502 : value_range r (TREE_TYPE (gimple_phi_result (phi)));
448 : 64336996 : for (unsigned x = 0; x < gimple_phi_num_args (phi); x++)
449 : 44956494 : prefill_name (r, gimple_phi_arg_def (phi, x));
450 : 19380502 : }
451 : : else
452 : : {
453 : 57112747 : gimple_range_op_handler handler (stmt);
454 : 57112747 : if (handler)
455 : : {
456 : 56991951 : tree op = handler.operand2 ();
457 : 56991951 : if (op)
458 : : {
459 : 37363937 : value_range r (TREE_TYPE (op));
460 : 37363937 : prefill_name (r, op);
461 : 37363937 : }
462 : 56991951 : op = handler.operand1 ();
463 : 56991951 : if (op)
464 : : {
465 : 56991111 : value_range r (TREE_TYPE (op));
466 : 56991111 : prefill_name (r, op);
467 : 56991111 : }
468 : : }
469 : : }
470 : : }
471 : 51569633 : if (idx)
472 : : {
473 : 0 : unsupported_range r;
474 : 0 : tracer.trailer (idx, "ROS ", false, ssa, r);
475 : 0 : }
476 : : }
477 : :
478 : :
479 : : // This routine will invoke the gimple fold_stmt routine, providing context to
480 : : // range_of_expr calls via an private internal API.
481 : :
482 : : bool
483 : 241239771 : gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
484 : : {
485 : 241239771 : gimple *stmt = gsi_stmt (*gsi);
486 : 241239771 : current_bb = gimple_bb (stmt);
487 : 241239771 : bool ret = ::fold_stmt (gsi, valueize);
488 : 241239771 : current_bb = NULL;
489 : 241239771 : return ret;
490 : : }
491 : :
492 : : // Called during dominator walks to register any inferred ranges that take
493 : : // effect from this point forward.
494 : :
495 : : void
496 : 256855040 : gimple_ranger::register_inferred_ranges (gimple *s)
497 : : {
498 : : // First, export the LHS if it is a new global range.
499 : 256855040 : tree lhs = gimple_get_lhs (s);
500 : 256855040 : if (lhs)
501 : : {
502 : 89384339 : value_range tmp (TREE_TYPE (lhs));
503 : 89384339 : if (range_of_stmt (tmp, s, lhs) && !tmp.varying_p ())
504 : 18438556 : set_range_info (lhs, tmp);
505 : 89384339 : }
506 : 256855040 : m_cache.apply_inferred_ranges (s);
507 : 256855040 : }
508 : :
509 : : // This function will walk the statements in BB to determine if any
510 : : // discovered inferred ranges in the block have any transitive effects,
511 : : // and if so, register those effects in BB.
512 : :
513 : : void
514 : 31339073 : gimple_ranger::register_transitive_inferred_ranges (basic_block bb)
515 : : {
516 : : // Return if there are no inferred ranges in BB.
517 : 31339073 : if (!infer_oracle ().has_range_p (bb))
518 : : return;
519 : :
520 : 2535341 : if (dump_file && (dump_flags & TDF_DETAILS))
521 : 12 : fprintf (dump_file, "Checking for transitive inferred ranges in BB %d\n",
522 : : bb->index);
523 : :
524 : 48702615 : for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
525 : 43631933 : gsi_next (&si))
526 : : {
527 : 43631933 : gimple *s = gsi_stmt (si);
528 : 43631933 : tree lhs = gimple_get_lhs (s);
529 : : // If the LHS already has an inferred effect, leave it be.
530 : 43631933 : if (!gimple_range_ssa_p (lhs) || infer_oracle ().has_range_p (bb, lhs))
531 : 34295219 : continue;
532 : : // Pick up global value.
533 : 9336714 : value_range g (TREE_TYPE (lhs));
534 : 9336714 : range_of_expr (g, lhs);
535 : :
536 : : // If either dependency has an inferred range, check if recalculating
537 : : // the LHS is different than the global value. If so, register it as
538 : : // an inferred range as well.
539 : 9336714 : value_range r (TREE_TYPE (lhs));
540 : 9336714 : r.set_undefined ();
541 : 9336714 : tree name1 = gori_ssa ()->depend1 (lhs);
542 : 9336714 : tree name2 = gori_ssa ()->depend2 (lhs);
543 : 4676290 : if ((name1 && infer_oracle ().has_range_p (bb, name1))
544 : 13700280 : || (name2 && infer_oracle ().has_range_p (bb, name2)))
545 : : {
546 : : // Check if folding S produces a different result.
547 : 631438 : if (fold_range (r, s, this) && g != r)
548 : : {
549 : 21579 : gimple_infer_range ir (lhs, r);
550 : 21579 : infer_oracle ().add_ranges (s, ir);
551 : 21579 : m_cache.register_inferred_value (r, lhs, bb);
552 : 21579 : }
553 : : }
554 : 9336714 : }
555 : : }
556 : :
557 : : // This is called to update ranger's concept of a global value for NAME
558 : : // with range R by an outside entity.
559 : :
560 : : void
561 : 11412799 : gimple_ranger::update_range_info (tree name, const vrange &r)
562 : : {
563 : 11412799 : value_range current (TREE_TYPE (name));
564 : 11412799 : m_cache.get_global_range (current, name);
565 : 11412799 : if (current.intersect (r))
566 : 253971 : m_cache.set_global_range (name, current, true);
567 : 11412799 : }
568 : :
569 : : // This routine will export whatever global ranges are known to GCC
570 : : // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
571 : :
572 : : void
573 : 2083114 : gimple_ranger::export_global_ranges ()
574 : : {
575 : 2083114 : if (dump_file)
576 : : {
577 : : /* Print the header only when there's something else
578 : : to print below. */
579 : 296 : fprintf (dump_file, "Exporting new global ranges:\n");
580 : 296 : fprintf (dump_file, "============================\n");
581 : : }
582 : 107299766 : for (unsigned x = 1; x < num_ssa_names; x++)
583 : : {
584 : 105216652 : tree name = ssa_name (x);
585 : 105216652 : if (!name)
586 : 28546468 : continue;
587 : 76670184 : value_range r (TREE_TYPE (name));
588 : 76670184 : if (name && !SSA_NAME_IN_FREE_LIST (name) && gimple_range_ssa_p (name)
589 : 44111078 : && m_cache.get_global_range (r, name) && !r.varying_p())
590 : 12591228 : set_range_info (name, r);
591 : 76670184 : }
592 : 2083114 : if (dump_file)
593 : 296 : fprintf (dump_file, "========= Done =============\n");
594 : 2083114 : }
595 : :
596 : : // Print the known table values to file F.
597 : :
598 : : void
599 : 248 : gimple_ranger::dump_bb (FILE *f, basic_block bb)
600 : : {
601 : 248 : unsigned x;
602 : 248 : edge_iterator ei;
603 : 248 : edge e;
604 : 248 : fprintf (f, "\n=========== BB %d ============\n", bb->index);
605 : 248 : m_cache.dump_bb (f, bb);
606 : :
607 : 248 : ::dump_bb (f, bb, 4, TDF_NONE);
608 : :
609 : : // Now find any globals defined in this block.
610 : 12593 : for (x = 1; x < num_ssa_names; x++)
611 : : {
612 : 12345 : tree name = ssa_name (x);
613 : 17557 : if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name))
614 : 7133 : continue;
615 : 5212 : value_range range (TREE_TYPE (name));
616 : 5212 : if (gimple_bb (SSA_NAME_DEF_STMT (name)) == bb
617 : 5212 : && m_cache.get_global_range (range, name))
618 : : {
619 : 288 : if (!range.varying_p ())
620 : : {
621 : 153 : print_generic_expr (f, name, TDF_SLIM);
622 : 153 : fprintf (f, " : ");
623 : 153 : range.dump (f);
624 : 153 : fprintf (f, "\n");
625 : : }
626 : :
627 : : }
628 : 5212 : }
629 : :
630 : : // And now outgoing edges, if they define anything.
631 : 609 : FOR_EACH_EDGE (e, ei, bb->succs)
632 : : {
633 : 20946 : for (x = 1; x < num_ssa_names; x++)
634 : : {
635 : 20585 : tree name = gimple_range_ssa_p (ssa_name (x));
636 : 20585 : if (!name || !gori ().has_edge_range_p (name, e))
637 : 19965 : continue;
638 : :
639 : 620 : value_range range (TREE_TYPE (name));
640 : 620 : if (m_cache.range_on_edge (range, e, name))
641 : : {
642 : 620 : gimple *s = SSA_NAME_DEF_STMT (name);
643 : 620 : value_range tmp_range (TREE_TYPE (name));
644 : : // Only print the range if this is the def block, or
645 : : // the on entry cache for either end of the edge is
646 : : // set.
647 : 946 : if ((s && bb == gimple_bb (s)) ||
648 : 1082 : m_cache.block_range (tmp_range, bb, name, false) ||
649 : 136 : m_cache.block_range (tmp_range, e->dest, name, false))
650 : : {
651 : 484 : if (!range.varying_p ())
652 : : {
653 : 426 : fprintf (f, "%d->%d ", e->src->index,
654 : 426 : e->dest->index);
655 : 426 : char c = ' ';
656 : 426 : if (e->flags & EDGE_TRUE_VALUE)
657 : 204 : fprintf (f, " (T)%c", c);
658 : 222 : else if (e->flags & EDGE_FALSE_VALUE)
659 : 222 : fprintf (f, " (F)%c", c);
660 : : else
661 : 0 : fprintf (f, " ");
662 : 426 : print_generic_expr (f, name, TDF_SLIM);
663 : 426 : fprintf(f, " : \t");
664 : 426 : range.dump(f);
665 : 426 : fprintf (f, "\n");
666 : : }
667 : : }
668 : 620 : }
669 : 620 : }
670 : : }
671 : 248 : }
672 : :
673 : : // Print the known table values to file F.
674 : :
675 : : void
676 : 45 : gimple_ranger::dump (FILE *f)
677 : : {
678 : 45 : basic_block bb;
679 : :
680 : 293 : FOR_EACH_BB_FN (bb, cfun)
681 : 248 : dump_bb (f, bb);
682 : :
683 : 45 : m_cache.dump (f);
684 : 45 : }
685 : :
686 : : void
687 : 0 : gimple_ranger::debug ()
688 : : {
689 : 0 : dump (stderr);
690 : 0 : }
691 : :
692 : : /* Create a new ranger instance and associate it with function FUN.
693 : : Each call must be paired with a call to disable_ranger to release
694 : : resources. */
695 : :
696 : : gimple_ranger *
697 : 21402577 : enable_ranger (struct function *fun, bool use_imm_uses)
698 : : {
699 : 21402577 : gimple_ranger *r;
700 : :
701 : 21402577 : gcc_checking_assert (!fun->x_range_query);
702 : 21402577 : r = new gimple_ranger (use_imm_uses);
703 : 21402577 : fun->x_range_query = r;
704 : :
705 : 21402577 : return r;
706 : : }
707 : :
708 : : /* Destroy and release the ranger instance associated with function FUN
709 : : and replace it the global ranger. */
710 : :
711 : : void
712 : 21402577 : disable_ranger (struct function *fun)
713 : : {
714 : 21402577 : gcc_checking_assert (fun->x_range_query);
715 : 21402577 : delete fun->x_range_query;
716 : 21402577 : fun->x_range_query = NULL;
717 : 21402577 : }
718 : :
719 : : // ---------------------------------------------------------------------------
720 : : //
721 : : // The DOM based ranger assumes a single DOM walk through the IL, and is
722 : : // used by the fvrp_folder as a fast VRP.
723 : : // During the dom walk, the current block has an ssa_lazy_cache pointer
724 : : // m_bb[bb->index] which represents all the cumulative contextual ranges
725 : : // active in the block.
726 : : // These ranges are pure static ranges generated by branches, and must be
727 : : // combined with the equivlaent global range to produce the final range.
728 : : // A NULL pointer means there are no contextual ranges.
729 : :
730 : : // Create a DOM based ranger for use by a DOM walk pass.
731 : :
732 : 6 : dom_ranger::dom_ranger () : m_global ()
733 : : {
734 : 6 : bitmap_obstack_initialize (&m_bitmaps);
735 : 6 : m_freelist.create (0);
736 : 6 : m_freelist.truncate (0);
737 : 6 : m_bb.create (0);
738 : 6 : m_bb.safe_grow_cleared (last_basic_block_for_fn (cfun));
739 : 6 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE))
740 : 0 : tracer.enable_trace ();
741 : 6 : }
742 : :
743 : : // Dispose of a DOM ranger.
744 : :
745 : 6 : dom_ranger::~dom_ranger ()
746 : : {
747 : 6 : if (dump_file && (dump_flags & TDF_DETAILS))
748 : : {
749 : 2 : fprintf (dump_file, "Non-varying global ranges:\n");
750 : 2 : fprintf (dump_file, "=========================:\n");
751 : 2 : m_global.dump (dump_file);
752 : : }
753 : 6 : m_bb.release ();
754 : 6 : m_freelist.release ();
755 : 6 : bitmap_obstack_release (&m_bitmaps);
756 : 6 : }
757 : :
758 : : // Implement range of EXPR on stmt S, and return it in R.
759 : : // Return false if no range can be calculated.
760 : :
761 : : bool
762 : 494 : dom_ranger::range_of_expr (vrange &r, tree expr, gimple *s)
763 : : {
764 : 494 : unsigned idx;
765 : 494 : if (!gimple_range_ssa_p (expr))
766 : 98 : return get_tree_range (r, expr, s);
767 : :
768 : 396 : if ((idx = tracer.header ("range_of_expr ")))
769 : : {
770 : 0 : print_generic_expr (dump_file, expr, TDF_SLIM);
771 : 0 : if (s)
772 : : {
773 : 0 : fprintf (dump_file, " at ");
774 : 0 : print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
775 : : }
776 : : else
777 : 0 : fprintf (dump_file, "\n");
778 : : }
779 : :
780 : : // If there is a statement, return the range in that statements block.
781 : 396 : if (s)
782 : 385 : range_in_bb (r, gimple_bb (s), expr);
783 : : else
784 : 11 : m_global.range_of_expr (r, expr, s);
785 : :
786 : 396 : if (idx)
787 : 0 : tracer.trailer (idx, " ", true, expr, r);
788 : : return true;
789 : : }
790 : :
791 : : // Return the range of EXPR on edge E in R.
792 : : // Return false if no range can be calculated.
793 : :
794 : : bool
795 : 28 : dom_ranger::range_on_edge (vrange &r, edge e, tree expr)
796 : : {
797 : 28 : if (!gimple_range_ssa_p (expr))
798 : 7 : return get_tree_range (r, expr, NULL, NULL, NULL, e);
799 : :
800 : 21 : basic_block bb = e->src;
801 : 21 : unsigned idx;
802 : 21 : if ((idx = tracer.header ("range_on_edge ")))
803 : : {
804 : 0 : fprintf (dump_file, "%d->%d for ",e->src->index, e->dest->index);
805 : 0 : print_generic_expr (dump_file, expr, TDF_SLIM);
806 : 0 : fputc ('\n',dump_file);
807 : : }
808 : :
809 : 21 : range_in_bb (r, bb, expr);
810 : 21 : value_range vr(TREE_TYPE (expr));
811 : 21 : if (gori_name_on_edge (vr, expr, e, this))
812 : 4 : r.intersect (vr);
813 : :
814 : 21 : if (idx)
815 : 0 : tracer.trailer (idx, " ", true, expr, r);
816 : 21 : return true;
817 : 21 : }
818 : :
819 : : // Return the range of NAME as it exists at the end of block BB in R.
820 : :
821 : : void
822 : 406 : dom_ranger::range_in_bb (vrange &r, basic_block bb, tree name)
823 : : {
824 : : // Start with the global value.
825 : 406 : m_global.range_of_expr (r, name);
826 : :
827 : : // If there is a contextual range, intersect it with the global range
828 : 406 : ssa_lazy_cache *context = m_bb[bb->index];
829 : 406 : if (context && context->has_range (name))
830 : : {
831 : 27 : value_range cr (TREE_TYPE (name));
832 : 27 : context->get_range (cr, name);
833 : 27 : r.intersect (cr);
834 : 27 : }
835 : 406 : }
836 : :
837 : : // Calculate the range of NAME, as the def of stmt S and return it in R.
838 : : // Return FALSE if no range can be calculated.
839 : : // Also set the global range for NAME as this should only be called within
840 : : // the def block during a DOM walk.
841 : :
842 : : bool
843 : 263 : dom_ranger::range_of_stmt (vrange &r, gimple *s, tree name)
844 : : {
845 : 263 : unsigned idx;
846 : 263 : bool ret;
847 : 263 : if (!name)
848 : 142 : name = gimple_get_lhs (s);
849 : :
850 : 263 : if (name && !gimple_range_ssa_p (name))
851 : 3 : return get_tree_range (r, name, NULL);
852 : :
853 : 260 : if ((idx = tracer.header ("range_of_stmt ")))
854 : 0 : print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
855 : :
856 : : // Its already been calculated.
857 : 260 : if (name && m_global.has_range (name))
858 : : {
859 : 115 : ret = m_global.range_of_expr (r, name, s);
860 : 115 : if (idx)
861 : 0 : tracer.trailer (idx, " Already had value ", ret, name, r);
862 : 115 : return ret;
863 : : }
864 : :
865 : : // Fold using a fur_depend object so that relations are registered.
866 : 145 : fold_using_range f;
867 : 145 : fur_depend src (s, this);
868 : 145 : ret = f.fold_stmt (r, s, src, name);
869 : :
870 : : // If there is a new calculated range and it is not varying, set
871 : : // a global range.
872 : 145 : if (ret && name && m_global.merge_range (name, r) && !r.varying_p ())
873 : 64 : set_range_info (name, r);
874 : :
875 : 145 : if (idx)
876 : 0 : tracer.trailer (idx, " ", ret, name, r);
877 : : return ret;
878 : : }
879 : :
880 : : // Preprocess block BB. If there is a single predecessor, start with any
881 : : // contextual ranges on the incoming edge, otherwise the initial list
882 : : // of ranges i empty for this block. Then Merge in any contextual ranges
883 : : // from the dominator block. Tihs will become the contextual ranges
884 : : // that apply to this block.
885 : :
886 : : void
887 : 25 : dom_ranger::pre_bb (basic_block bb)
888 : : {
889 : 25 : if (dump_file && (dump_flags & TDF_DETAILS))
890 : 15 : fprintf (dump_file, "#FVRP entering BB %d\n", bb->index);
891 : :
892 : 25 : m_bb[bb->index] = NULL;
893 : 25 : basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
894 : :
895 : 25 : ssa_lazy_cache *e_cache;
896 : 25 : if (!m_freelist.is_empty ())
897 : 16 : e_cache = m_freelist.pop ();
898 : : else
899 : 9 : e_cache = new ssa_lazy_cache (&m_bitmaps);
900 : 25 : gcc_checking_assert (e_cache->empty_p ());
901 : :
902 : : // If there is a single pred, check if there are any ranges on
903 : : // the edge and start with those.
904 : 25 : if (single_pred_p (bb))
905 : : {
906 : 14 : gori_on_edge (*e_cache, EDGE_PRED (bb, 0), this);
907 : 14 : if (!e_cache->empty_p () && dump_file && (dump_flags & TDF_DETAILS))
908 : : {
909 : 10 : fprintf (dump_file, "\nEdge ranges BB %d->%d\n",
910 : 5 : EDGE_PRED (bb, 0)->src->index, bb->index);
911 : 5 : e_cache->dump(dump_file);
912 : : }
913 : : }
914 : : // If the dominator had any ranges registered, integrate those.
915 : 25 : if (dom_bb && m_bb [dom_bb->index])
916 : 7 : e_cache->merge (*(m_bb[dom_bb->index]));
917 : :
918 : : // If there are no ranges, this block has no contextual ranges.
919 : 25 : if (e_cache->empty_p ())
920 : 14 : m_freelist.safe_push (e_cache);
921 : : else
922 : 11 : m_bb[bb->index] = e_cache;
923 : :
924 : 25 : if (dump_file && (dump_flags & TDF_DETAILS))
925 : : {
926 : 15 : if (m_bb[bb->index])
927 : : {
928 : 9 : fprintf (dump_file, "all contextual ranges active:\n");
929 : 9 : m_bb[bb->index]->dump (dump_file);
930 : : }
931 : : else
932 : 6 : fprintf (dump_file, " NO contextual ranges active:\n");
933 : : }
934 : 25 : }
935 : :
936 : : // Perform any post block processing.
937 : :
938 : : void
939 : 25 : dom_ranger::post_bb (basic_block bb)
940 : : {
941 : 25 : if (dump_file && (dump_flags & TDF_DETAILS))
942 : 15 : fprintf (dump_file, "#FVRP POST BB %d\n", bb->index);
943 : : // If there were contextual ranges, clear them and put the
944 : : // object on the freelist.
945 : 25 : if (m_bb[bb->index])
946 : : {
947 : 11 : m_bb[bb->index]->clear ();
948 : 11 : m_freelist.safe_push (m_bb[bb->index]);
949 : 11 : m_bb[bb->index] = NULL;
950 : : }
951 : 25 : }
|
