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