Line data Source code
1 : /* Gimple ranger SSA cache implementation.
2 : Copyright (C) 2017-2026 Free Software Foundation, Inc.
3 : Contributed by Andrew MacLeod <amacleod@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify
8 : it under the terms of the GNU General Public License as published by
9 : the Free Software Foundation; either version 3, or (at your option)
10 : any later version.
11 :
12 : GCC is distributed in the hope that it will be useful,
13 : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : GNU General Public License for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "backend.h"
25 : #include "insn-codes.h"
26 : #include "tree.h"
27 : #include "gimple.h"
28 : #include "ssa.h"
29 : #include "gimple-pretty-print.h"
30 : #include "gimple-range.h"
31 : #include "value-range-storage.h"
32 : #include "tree-cfg.h"
33 : #include "target.h"
34 : #include "attribs.h"
35 : #include "gimple-iterator.h"
36 : #include "gimple-walk.h"
37 : #include "cfganal.h"
38 :
39 : #define DEBUG_RANGE_CACHE (dump_file \
40 : && (param_ranger_debug & RANGER_DEBUG_CACHE))
41 :
42 : // This class represents the API into a cache of ranges for an SSA_NAME.
43 : // Routines must be implemented to set, get, and query if a value is set.
44 :
45 : class ssa_block_ranges
46 : {
47 : public:
48 29164361 : ssa_block_ranges (tree t) : m_type (t) { }
49 : virtual bool set_bb_range (const_basic_block bb, const vrange &r) = 0;
50 : virtual bool get_bb_range (vrange &r, const_basic_block bb) = 0;
51 : virtual bool bb_range_p (const_basic_block bb) = 0;
52 :
53 : void dump(FILE *f);
54 : private:
55 : tree m_type;
56 : };
57 :
58 : // Print the list of known ranges for file F in a nice format.
59 :
60 : void
61 0 : ssa_block_ranges::dump (FILE *f)
62 : {
63 0 : basic_block bb;
64 0 : value_range r (m_type);
65 :
66 0 : FOR_EACH_BB_FN (bb, cfun)
67 0 : if (get_bb_range (r, bb))
68 : {
69 0 : fprintf (f, "BB%d -> ", bb->index);
70 0 : r.dump (f);
71 0 : fprintf (f, "\n");
72 : }
73 0 : }
74 :
75 : // This class implements the range cache as a linear vector, indexed by BB.
76 : // It caches a varying and undefined range which are used instead of
77 : // allocating new ones each time.
78 :
79 : class sbr_vector : public ssa_block_ranges
80 : {
81 : public:
82 : sbr_vector (tree t, vrange_allocator *allocator, bool zero_p = true);
83 :
84 : virtual bool set_bb_range (const_basic_block bb, const vrange &r) override;
85 : virtual bool get_bb_range (vrange &r, const_basic_block bb) override;
86 : virtual bool bb_range_p (const_basic_block bb) override;
87 : protected:
88 : vrange_storage **m_tab; // Non growing vector.
89 : int m_tab_size;
90 : vrange_storage *m_varying;
91 : vrange_storage *m_undefined;
92 : tree m_type;
93 : vrange_allocator *m_range_allocator;
94 : bool m_zero_p;
95 : void grow ();
96 : };
97 :
98 :
99 : // Initialize a block cache for an ssa_name of type T.
100 :
101 29059151 : sbr_vector::sbr_vector (tree t, vrange_allocator *allocator, bool zero_p)
102 29059151 : : ssa_block_ranges (t)
103 : {
104 29059151 : gcc_checking_assert (TYPE_P (t));
105 29059151 : m_type = t;
106 29059151 : m_zero_p = zero_p;
107 29059151 : m_range_allocator = allocator;
108 29059151 : m_tab_size = last_basic_block_for_fn (cfun) + 1;
109 58118302 : m_tab = static_cast <vrange_storage **>
110 29059151 : (allocator->alloc (m_tab_size * sizeof (vrange_storage *)));
111 29059151 : if (zero_p)
112 25533264 : memset (m_tab, 0, m_tab_size * sizeof (vrange *));
113 :
114 : // Create the cached type range.
115 29059151 : m_varying = m_range_allocator->clone_varying (t);
116 29059151 : m_undefined = m_range_allocator->clone_undefined (t);
117 29059151 : }
118 :
119 : // Grow the vector when the CFG has increased in size.
120 :
121 : void
122 10075 : sbr_vector::grow ()
123 : {
124 10075 : int curr_bb_size = last_basic_block_for_fn (cfun);
125 10075 : gcc_checking_assert (curr_bb_size > m_tab_size);
126 :
127 : // Increase the max of a)128, b)needed increase * 2, c)10% of current_size.
128 10075 : int inc = MAX ((curr_bb_size - m_tab_size) * 2, 128);
129 10075 : inc = MAX (inc, curr_bb_size / 10);
130 10075 : int new_size = inc + curr_bb_size;
131 :
132 : // Allocate new memory, copy the old vector and clear the new space.
133 10075 : vrange_storage **t = static_cast <vrange_storage **>
134 10075 : (m_range_allocator->alloc (new_size * sizeof (vrange_storage *)));
135 10075 : memcpy (t, m_tab, m_tab_size * sizeof (vrange_storage *));
136 10075 : if (m_zero_p)
137 7938 : memset (t + m_tab_size, 0, (new_size - m_tab_size) * sizeof (vrange_storage *));
138 :
139 10075 : m_tab = t;
140 10075 : m_tab_size = new_size;
141 10075 : }
142 :
143 : // Set the range for block BB to be R.
144 :
145 : bool
146 76290128 : sbr_vector::set_bb_range (const_basic_block bb, const vrange &r)
147 : {
148 76290128 : vrange_storage *m;
149 76290128 : if (bb->index >= m_tab_size)
150 10075 : grow ();
151 76290128 : if (r.varying_p ())
152 23702371 : m = m_varying;
153 52587757 : else if (r.undefined_p ())
154 5316995 : m = m_undefined;
155 : else
156 47270762 : m = m_range_allocator->clone (r);
157 76290128 : m_tab[bb->index] = m;
158 76290128 : return true;
159 : }
160 :
161 : // Return the range associated with block BB in R. Return false if
162 : // there is no range.
163 :
164 : bool
165 339601837 : sbr_vector::get_bb_range (vrange &r, const_basic_block bb)
166 : {
167 339601837 : if (bb->index >= m_tab_size)
168 : return false;
169 339593950 : vrange_storage *m = m_tab[bb->index];
170 339593950 : if (m)
171 : {
172 256200763 : m->get_vrange (r, m_type);
173 256200763 : return true;
174 : }
175 : return false;
176 : }
177 :
178 : // Return true if a range is present.
179 :
180 : bool
181 251332118 : sbr_vector::bb_range_p (const_basic_block bb)
182 : {
183 251332118 : if (bb->index < m_tab_size)
184 251321339 : return m_tab[bb->index] != NULL;
185 : return false;
186 : }
187 :
188 : // Like an sbr_vector, except it uses a bitmap to manage whether value is set
189 : // or not rather than cleared memory.
190 :
191 : class sbr_lazy_vector : public sbr_vector
192 : {
193 : public:
194 : sbr_lazy_vector (tree t, vrange_allocator *allocator, bitmap_obstack *bm);
195 :
196 : virtual bool set_bb_range (const_basic_block bb, const vrange &r) override;
197 : virtual bool get_bb_range (vrange &r, const_basic_block bb) override;
198 : virtual bool bb_range_p (const_basic_block bb) override;
199 : protected:
200 : bitmap m_has_value;
201 : };
202 :
203 3525887 : sbr_lazy_vector::sbr_lazy_vector (tree t, vrange_allocator *allocator,
204 : bitmap_obstack *bm)
205 3525887 : : sbr_vector (t, allocator, false)
206 : {
207 3525887 : m_has_value = BITMAP_ALLOC (bm);
208 3525887 : }
209 :
210 : bool
211 12014283 : sbr_lazy_vector::set_bb_range (const_basic_block bb, const vrange &r)
212 : {
213 12014283 : sbr_vector::set_bb_range (bb, r);
214 12014283 : bitmap_set_bit (m_has_value, bb->index);
215 12014283 : return true;
216 : }
217 :
218 : bool
219 293890183 : sbr_lazy_vector::get_bb_range (vrange &r, const_basic_block bb)
220 : {
221 293890183 : if (bitmap_bit_p (m_has_value, bb->index))
222 42272246 : return sbr_vector::get_bb_range (r, bb);
223 : return false;
224 : }
225 :
226 : bool
227 45971186 : sbr_lazy_vector::bb_range_p (const_basic_block bb)
228 : {
229 45971186 : return bitmap_bit_p (m_has_value, bb->index);
230 : }
231 :
232 : // This class implements the on entry cache via a sparse bitmap.
233 : // It uses the quad bit routines to access 4 bits at a time.
234 : // A value of 0 (the default) means there is no entry, and a value of
235 : // 1 thru SBR_NUM represents an element in the m_range vector.
236 : // Varying is given the first value (1) and pre-cached.
237 : // SBR_NUM + 1 represents the value of UNDEFINED, and is never stored.
238 : // SBR_NUM is the number of values that can be cached.
239 : // Indexes are 1..SBR_NUM and are stored locally at m_range[0..SBR_NUM-1]
240 :
241 : #define SBR_NUM 14
242 : #define SBR_UNDEF SBR_NUM + 1
243 : #define SBR_VARYING 1
244 :
245 : class sbr_sparse_bitmap : public ssa_block_ranges
246 : {
247 : public:
248 : sbr_sparse_bitmap (tree t, vrange_allocator *allocator, bitmap_obstack *bm);
249 : virtual bool set_bb_range (const_basic_block bb, const vrange &r) override;
250 : virtual bool get_bb_range (vrange &r, const_basic_block bb) override;
251 : virtual bool bb_range_p (const_basic_block bb) override;
252 : private:
253 : void bitmap_set_quad (bitmap head, int quad, int quad_value);
254 : int bitmap_get_quad (const_bitmap head, int quad);
255 : vrange_allocator *m_range_allocator;
256 : vrange_storage *m_range[SBR_NUM];
257 : bitmap_head bitvec;
258 : tree m_type;
259 : };
260 :
261 : // Initialize a block cache for an ssa_name of type T.
262 :
263 105210 : sbr_sparse_bitmap::sbr_sparse_bitmap (tree t, vrange_allocator *allocator,
264 : bitmap_obstack *bm)
265 105210 : : ssa_block_ranges (t)
266 : {
267 105210 : gcc_checking_assert (TYPE_P (t));
268 105210 : m_type = t;
269 105210 : bitmap_initialize (&bitvec, bm);
270 105210 : bitmap_tree_view (&bitvec);
271 105210 : m_range_allocator = allocator;
272 : // Pre-cache varying.
273 105210 : m_range[0] = m_range_allocator->clone_varying (t);
274 : // Pre-cache zero and non-zero values for pointers.
275 105210 : if (POINTER_TYPE_P (t))
276 : {
277 1511 : prange nonzero;
278 1511 : nonzero.set_nonzero (t);
279 1511 : m_range[1] = m_range_allocator->clone (nonzero);
280 1511 : prange zero;
281 1511 : zero.set_zero (t);
282 1511 : m_range[2] = m_range_allocator->clone (zero);
283 1511 : }
284 : else
285 103699 : m_range[1] = m_range[2] = NULL;
286 : // Clear SBR_NUM entries.
287 1262520 : for (int x = 3; x < SBR_NUM; x++)
288 1157310 : m_range[x] = 0;
289 105210 : }
290 :
291 : // Set 4 bit values in a sparse bitmap. This allows a bitmap to
292 : // function as a sparse array of 4 bit values.
293 : // QUAD is the index, QUAD_VALUE is the 4 bit value to set.
294 :
295 : inline void
296 498563 : sbr_sparse_bitmap::bitmap_set_quad (bitmap head, int quad, int quad_value)
297 : {
298 498563 : bitmap_set_aligned_chunk (head, quad, 4, (BITMAP_WORD) quad_value);
299 : }
300 :
301 : // Get a 4 bit value from a sparse bitmap. This allows a bitmap to
302 : // function as a sparse array of 4 bit values.
303 : // QUAD is the index.
304 : inline int
305 15424061 : sbr_sparse_bitmap::bitmap_get_quad (const_bitmap head, int quad)
306 : {
307 30848122 : return (int) bitmap_get_aligned_chunk (head, quad, 4);
308 : }
309 :
310 : // Set the range on entry to basic block BB to R.
311 :
312 : bool
313 498563 : sbr_sparse_bitmap::set_bb_range (const_basic_block bb, const vrange &r)
314 : {
315 498563 : if (r.undefined_p ())
316 : {
317 29045 : bitmap_set_quad (&bitvec, bb->index, SBR_UNDEF);
318 29045 : return true;
319 : }
320 :
321 : // Loop thru the values to see if R is already present.
322 879529 : for (int x = 0; x < SBR_NUM; x++)
323 868523 : if (!m_range[x] || m_range[x]->equal_p (r))
324 : {
325 458512 : if (!m_range[x])
326 119037 : m_range[x] = m_range_allocator->clone (r);
327 458512 : bitmap_set_quad (&bitvec, bb->index, x + 1);
328 458512 : return true;
329 : }
330 : // All values are taken, default to VARYING.
331 11006 : bitmap_set_quad (&bitvec, bb->index, SBR_VARYING);
332 11006 : return false;
333 : }
334 :
335 : // Return the range associated with block BB in R. Return false if
336 : // there is no range.
337 :
338 : bool
339 12927006 : sbr_sparse_bitmap::get_bb_range (vrange &r, const_basic_block bb)
340 : {
341 12927006 : int value = bitmap_get_quad (&bitvec, bb->index);
342 :
343 12927006 : if (!value)
344 : return false;
345 :
346 1955238 : gcc_checking_assert (value <= SBR_UNDEF);
347 1955238 : if (value == SBR_UNDEF)
348 70284 : r.set_undefined ();
349 : else
350 1884954 : m_range[value - 1]->get_vrange (r, m_type);
351 : return true;
352 : }
353 :
354 : // Return true if a range is present.
355 :
356 : bool
357 2497055 : sbr_sparse_bitmap::bb_range_p (const_basic_block bb)
358 : {
359 2497055 : return (bitmap_get_quad (&bitvec, bb->index) != 0);
360 : }
361 :
362 : // -------------------------------------------------------------------------
363 :
364 : // Initialize the block cache.
365 :
366 29420773 : block_range_cache::block_range_cache ()
367 : {
368 29420773 : bitmap_obstack_initialize (&m_bitmaps);
369 29420773 : m_ssa_ranges.create (0);
370 58841546 : m_ssa_ranges.safe_grow_cleared (num_ssa_names);
371 29420773 : m_range_allocator = new vrange_allocator;
372 29420773 : }
373 :
374 : // Remove any m_block_caches which have been created.
375 :
376 29420773 : block_range_cache::~block_range_cache ()
377 : {
378 29420773 : delete m_range_allocator;
379 : // Release the vector itself.
380 29420773 : m_ssa_ranges.release ();
381 29420773 : bitmap_obstack_release (&m_bitmaps);
382 29420773 : }
383 :
384 : // Clear block info for NAME.
385 :
386 : void
387 1157 : block_range_cache::clear (tree name)
388 : {
389 1157 : unsigned v = SSA_NAME_VERSION (name);
390 1157 : if (v >= m_ssa_ranges.length ())
391 : return;
392 1157 : m_ssa_ranges[v] = NULL;
393 : }
394 :
395 : // Set the range for NAME on entry to block BB to R.
396 : // If it has not been accessed yet, allocate it first.
397 :
398 : bool
399 76788691 : block_range_cache::set_bb_range (tree name, const_basic_block bb,
400 : const vrange &r)
401 : {
402 76788691 : unsigned v = SSA_NAME_VERSION (name);
403 76788691 : if (v >= m_ssa_ranges.length ())
404 2 : m_ssa_ranges.safe_grow_cleared (num_ssa_names);
405 :
406 76788691 : if (!m_ssa_ranges[v])
407 : {
408 : // Use sparse bitmap representation if there are too many basic blocks.
409 29164361 : if (last_basic_block_for_fn (cfun) > param_vrp_sparse_threshold)
410 : {
411 105210 : void *r = m_range_allocator->alloc (sizeof (sbr_sparse_bitmap));
412 105210 : m_ssa_ranges[v] = new (r) sbr_sparse_bitmap (TREE_TYPE (name),
413 : m_range_allocator,
414 105210 : &m_bitmaps);
415 : }
416 29059151 : else if (last_basic_block_for_fn (cfun) < param_vrp_vector_threshold)
417 : {
418 : // For small CFGs use the basic vector implementation.
419 25533264 : void *r = m_range_allocator->alloc (sizeof (sbr_vector));
420 25533264 : m_ssa_ranges[v] = new (r) sbr_vector (TREE_TYPE (name),
421 25533264 : m_range_allocator);
422 : }
423 : else
424 : {
425 : // Otherwise use the sparse vector implementation.
426 3525887 : void *r = m_range_allocator->alloc (sizeof (sbr_lazy_vector));
427 3525887 : m_ssa_ranges[v] = new (r) sbr_lazy_vector (TREE_TYPE (name),
428 : m_range_allocator,
429 3525887 : &m_bitmaps);
430 : }
431 : }
432 76788691 : return m_ssa_ranges[v]->set_bb_range (bb, r);
433 : }
434 :
435 :
436 : // Return a pointer to the ssa_block_cache for NAME. If it has not been
437 : // accessed yet, return NULL.
438 :
439 : inline ssa_block_ranges *
440 1209202788 : block_range_cache::query_block_ranges (tree name)
441 : {
442 1209202788 : unsigned v = SSA_NAME_VERSION (name);
443 1209202788 : if (v >= m_ssa_ranges.length () || !m_ssa_ranges[v])
444 : return NULL;
445 903945893 : return m_ssa_ranges[v];
446 : }
447 :
448 :
449 :
450 : // Return the range for NAME on entry to BB in R. Return true if there
451 : // is one.
452 :
453 : bool
454 813113319 : block_range_cache::get_bb_range (vrange &r, tree name, const_basic_block bb)
455 : {
456 813113319 : ssa_block_ranges *ptr = query_block_ranges (name);
457 813113319 : if (ptr)
458 604145534 : return ptr->get_bb_range (r, bb);
459 : return false;
460 : }
461 :
462 : // Return true if NAME has a range set in block BB.
463 :
464 : bool
465 396089469 : block_range_cache::bb_range_p (tree name, const_basic_block bb)
466 : {
467 396089469 : ssa_block_ranges *ptr = query_block_ranges (name);
468 396089469 : if (ptr)
469 299800359 : return ptr->bb_range_p (bb);
470 : return false;
471 : }
472 :
473 : // Print all known block caches to file F.
474 :
475 : void
476 0 : block_range_cache::dump (FILE *f)
477 : {
478 0 : unsigned x;
479 0 : for (x = 1; x < m_ssa_ranges.length (); ++x)
480 : {
481 0 : if (m_ssa_ranges[x])
482 : {
483 0 : fprintf (f, " Ranges for ");
484 0 : print_generic_expr (f, ssa_name (x), TDF_NONE);
485 0 : fprintf (f, ":\n");
486 0 : m_ssa_ranges[x]->dump (f);
487 0 : fprintf (f, "\n");
488 : }
489 : }
490 0 : }
491 :
492 : // Print all known ranges on entry to block BB to file F.
493 :
494 : void
495 257 : block_range_cache::dump (FILE *f, basic_block bb, bool print_varying)
496 : {
497 257 : unsigned x;
498 257 : bool summarize_varying = false;
499 12507 : for (x = 1; x < m_ssa_ranges.length (); ++x)
500 : {
501 12250 : if (!m_ssa_ranges[x])
502 11004 : continue;
503 :
504 1246 : if (!gimple_range_ssa_p (ssa_name (x)))
505 0 : continue;
506 :
507 1246 : value_range r (TREE_TYPE (ssa_name (x)));
508 1246 : if (m_ssa_ranges[x]->get_bb_range (r, bb))
509 : {
510 222 : if (!print_varying && r.varying_p ())
511 : {
512 0 : summarize_varying = true;
513 0 : continue;
514 : }
515 222 : print_generic_expr (f, ssa_name (x), TDF_NONE);
516 222 : fprintf (f, "\t");
517 222 : r.dump(f);
518 222 : fprintf (f, "\n");
519 : }
520 1246 : }
521 : // If there were any varying entries, lump them all together.
522 257 : if (summarize_varying)
523 : {
524 0 : fprintf (f, "VARYING_P on entry : ");
525 0 : for (x = 1; x < m_ssa_ranges.length (); ++x)
526 : {
527 0 : if (!m_ssa_ranges[x])
528 0 : continue;
529 :
530 0 : if (!gimple_range_ssa_p (ssa_name (x)))
531 0 : continue;
532 :
533 0 : value_range r (TREE_TYPE (ssa_name (x)));
534 0 : if (m_ssa_ranges[x]->get_bb_range (r, bb))
535 : {
536 0 : if (r.varying_p ())
537 : {
538 0 : print_generic_expr (f, ssa_name (x), TDF_NONE);
539 0 : fprintf (f, " ");
540 : }
541 : }
542 0 : }
543 0 : fprintf (f, "\n");
544 : }
545 257 : }
546 :
547 : // -------------------------------------------------------------------------
548 :
549 : // Initialize an ssa cache.
550 :
551 61181757 : ssa_cache::ssa_cache ()
552 : {
553 61181757 : m_tab.create (0);
554 61181757 : m_range_allocator = new vrange_allocator;
555 61181757 : }
556 :
557 : // Deconstruct an ssa cache.
558 :
559 61181745 : ssa_cache::~ssa_cache ()
560 : {
561 61181745 : m_tab.release ();
562 61181745 : delete m_range_allocator;
563 61181745 : }
564 :
565 : // Enable a query to evaluate staements/ramnges based on picking up ranges
566 : // from just an ssa-cache.
567 :
568 : bool
569 3958 : ssa_cache::range_of_expr (vrange &r, tree expr, gimple *stmt)
570 : {
571 3958 : if (!gimple_range_ssa_p (expr))
572 0 : return get_tree_range (r, expr, stmt);
573 :
574 3958 : if (!get_range (r, expr))
575 53 : gimple_range_global (r, expr, cfun);
576 : return true;
577 : }
578 :
579 : // Return TRUE if the global range of NAME has a cache entry.
580 :
581 : bool
582 11342932 : ssa_cache::has_range (tree name) const
583 : {
584 11342932 : unsigned v = SSA_NAME_VERSION (name);
585 11342932 : if (v >= m_tab.length ())
586 : return false;
587 10873792 : return m_tab[v] != NULL;
588 : }
589 :
590 : // Retrieve the global range of NAME from cache memory if it exists.
591 : // Return the value in R.
592 :
593 : bool
594 1223465758 : ssa_cache::get_range (vrange &r, tree name) const
595 : {
596 1223465758 : unsigned v = SSA_NAME_VERSION (name);
597 1223465758 : if (v >= m_tab.length ())
598 : return false;
599 :
600 1211435876 : vrange_storage *stow = m_tab[v];
601 1211435876 : if (!stow)
602 : return false;
603 993003590 : stow->get_vrange (r, TREE_TYPE (name));
604 993003590 : return true;
605 : }
606 :
607 : // Set the range for NAME to R in the ssa cache.
608 : // Return TRUE if there was already a range set, otherwise false.
609 :
610 : bool
611 156674451 : ssa_cache::set_range (tree name, const vrange &r)
612 : {
613 156674451 : unsigned v = SSA_NAME_VERSION (name);
614 156674451 : if (v >= m_tab.length ())
615 15837234 : m_tab.safe_grow_cleared (num_ssa_names + 1);
616 :
617 156674451 : vrange_storage *m = m_tab[v];
618 156674451 : if (m && m->fits_p (r))
619 22704111 : m->set_vrange (r);
620 : else
621 133970340 : m_tab[v] = m_range_allocator->clone (r);
622 156674451 : return m != NULL;
623 : }
624 :
625 : // If NAME has a range, intersect it with R, otherwise set it to R.
626 : // Return TRUE if the range is new or changes.
627 :
628 : bool
629 401 : ssa_cache::merge_range (tree name, const vrange &r)
630 : {
631 401 : unsigned v = SSA_NAME_VERSION (name);
632 401 : if (v >= m_tab.length ())
633 18 : m_tab.safe_grow_cleared (num_ssa_names + 1);
634 :
635 401 : vrange_storage *m = m_tab[v];
636 : // Check if this is a new value.
637 401 : if (!m)
638 400 : m_tab[v] = m_range_allocator->clone (r);
639 : else
640 : {
641 1 : value_range curr (TREE_TYPE (name));
642 1 : m->get_vrange (curr, TREE_TYPE (name));
643 : // If there is no change, return false.
644 1 : if (!curr.intersect (r))
645 1 : return false;
646 :
647 0 : if (m->fits_p (curr))
648 0 : m->set_vrange (curr);
649 : else
650 0 : m_tab[v] = m_range_allocator->clone (curr);
651 1 : }
652 : return true;
653 : }
654 :
655 : // Set the range for NAME to R in the ssa cache.
656 :
657 : void
658 1157 : ssa_cache::clear_range (tree name)
659 : {
660 1157 : unsigned v = SSA_NAME_VERSION (name);
661 1157 : if (v >= m_tab.length ())
662 : return;
663 1157 : m_tab[v] = NULL;
664 : }
665 :
666 : // Clear the ssa cache.
667 :
668 : void
669 0 : ssa_cache::clear ()
670 : {
671 0 : if (m_tab.address ())
672 0 : memset (m_tab.address(), 0, m_tab.length () * sizeof (vrange *));
673 0 : }
674 :
675 : // Dump the contents of the ssa cache to F.
676 :
677 : void
678 64 : ssa_cache::dump (FILE *f)
679 : {
680 3223 : for (unsigned x = 1; x < num_ssa_names; x++)
681 : {
682 3159 : if (!gimple_range_ssa_p (ssa_name (x)))
683 1275 : continue;
684 1884 : value_range r (TREE_TYPE (ssa_name (x)));
685 : // Dump all non-varying ranges.
686 1884 : if (get_range (r, ssa_name (x)) && !r.varying_p ())
687 : {
688 304 : print_generic_expr (f, ssa_name (x), TDF_NONE);
689 304 : fprintf (f, " : ");
690 304 : r.dump (f);
691 304 : fprintf (f, "\n");
692 : }
693 1884 : }
694 :
695 64 : }
696 :
697 : // Construct an ssa_lazy_cache. If OB is specified, us it, otherwise use
698 : // a local bitmap obstack.
699 :
700 31760975 : ssa_lazy_cache::ssa_lazy_cache (bitmap_obstack *ob)
701 : {
702 31760975 : if (!ob)
703 : {
704 31760963 : bitmap_obstack_initialize (&m_bitmaps);
705 31760963 : m_ob = &m_bitmaps;
706 : }
707 : else
708 12 : m_ob = ob;
709 31760975 : active_p = BITMAP_ALLOC (m_ob);
710 31760975 : }
711 :
712 : // Destruct an sa_lazy_cache. Free the bitmap if it came from a different
713 : // obstack, or release the obstack if it was a local one.
714 :
715 31760963 : ssa_lazy_cache::~ssa_lazy_cache ()
716 : {
717 31760963 : if (m_ob == &m_bitmaps)
718 31760963 : bitmap_obstack_release (&m_bitmaps);
719 : else
720 0 : BITMAP_FREE (active_p);
721 31760963 : }
722 :
723 : // Return true if NAME has an active range in the cache.
724 :
725 : bool
726 717 : ssa_lazy_cache::has_range (tree name) const
727 : {
728 717 : return bitmap_bit_p (active_p, SSA_NAME_VERSION (name));
729 : }
730 :
731 : // Set range of NAME to R in a lazy cache. Return FALSE if it did not already
732 : // have a range.
733 :
734 : bool
735 116502063 : ssa_lazy_cache::set_range (tree name, const vrange &r)
736 : {
737 116502063 : unsigned v = SSA_NAME_VERSION (name);
738 116502063 : if (!bitmap_set_bit (active_p, v))
739 : {
740 : // There is already an entry, simply set it.
741 13869767 : gcc_checking_assert (v < m_tab.length ());
742 13869767 : return ssa_cache::set_range (name, r);
743 : }
744 102632296 : if (v >= m_tab.length ())
745 55362642 : m_tab.safe_grow (num_ssa_names + 1);
746 102632296 : m_tab[v] = m_range_allocator->clone (r);
747 102632296 : return false;
748 : }
749 :
750 : // If NAME has a range, intersect it with R, otherwise set it to R.
751 : // Return TRUE if the range is new or changes.
752 :
753 : bool
754 213 : ssa_lazy_cache::merge_range (tree name, const vrange &r)
755 : {
756 213 : unsigned v = SSA_NAME_VERSION (name);
757 213 : if (!bitmap_set_bit (active_p, v))
758 : {
759 : // There is already an entry, simply merge it.
760 1 : gcc_checking_assert (v < m_tab.length ());
761 1 : return ssa_cache::merge_range (name, r);
762 : }
763 212 : if (v >= m_tab.length ())
764 160 : m_tab.safe_grow (num_ssa_names + 1);
765 212 : m_tab[v] = m_range_allocator->clone (r);
766 212 : return true;
767 : }
768 :
769 : // Merge all elements of CACHE with this cache.
770 : // Any names in CACHE that are not in this one are added.
771 : // Any names in both are merged via merge_range..
772 :
773 : void
774 7 : ssa_lazy_cache::merge (const ssa_lazy_cache &cache)
775 : {
776 7 : unsigned x;
777 7 : bitmap_iterator bi;
778 57 : EXECUTE_IF_SET_IN_BITMAP (cache.active_p, 0, x, bi)
779 : {
780 50 : tree name = ssa_name (x);
781 50 : value_range r(TREE_TYPE (name));
782 50 : cache.get_range (r, name);
783 50 : merge_range (ssa_name (x), r);
784 50 : }
785 7 : }
786 :
787 : // Return TRUE if NAME has a range, and return it in R.
788 :
789 : bool
790 316449235 : ssa_lazy_cache::get_range (vrange &r, tree name) const
791 : {
792 316449235 : if (!bitmap_bit_p (active_p, SSA_NAME_VERSION (name)))
793 : return false;
794 138472496 : return ssa_cache::get_range (r, name);
795 : }
796 :
797 : // Remove NAME from the active range list.
798 :
799 : void
800 61081729 : ssa_lazy_cache::clear_range (tree name)
801 : {
802 61081729 : bitmap_clear_bit (active_p, SSA_NAME_VERSION (name));
803 61081729 : }
804 :
805 : // Remove all ranges from the active range list.
806 :
807 : void
808 38425518 : ssa_lazy_cache::clear ()
809 : {
810 38425518 : bitmap_clear (active_p);
811 38425518 : }
812 :
813 : // --------------------------------------------------------------------------
814 :
815 : // A cache timestamp has two components.
816 : //
817 : // STORED and CALC are maintained separately. STORED is updated only when
818 : // the cached value actually changes, while CALC is updated every time the
819 : // value is recalculated.
820 : //
821 : // This allows stale values to be recalculated without forcing dependent
822 : // values to be recalculated as well. If a recalculation produces the same
823 : // value, only CALC changes and the STORED timestamp remains unchanged,
824 : // indicating that the observable value has not changed.
825 :
826 : struct time_stamp
827 : {
828 : unsigned stored; // Timestamp of last time value was SET.
829 : unsigned calc; // Timestamp when the value was calcuclated last.
830 : };
831 :
832 : // Manage dependency timestamps for SSA names.
833 : //
834 : // Each SSA name records when its value last changed (stored) and when it
835 : // was last recalculated (calc). Dependencies are current if their stored
836 : // timestamps are no newer than the dependent value. Recalculating a value
837 : // without changing it updates only the calc timestamp, avoiding unnecessary
838 : // invalidation of dependent values.
839 : // always_current is managed by setting the calcualted timestamp to 0.
840 :
841 : class temporal_cache
842 : {
843 : public:
844 : temporal_cache ();
845 : ~temporal_cache ();
846 : bool current_p (tree name, tree dep1, tree dep2) const;
847 : void set_timestamp_stored (tree name);
848 : void set_timestamp_calc (tree name);
849 : void set_always_current (tree name);
850 : bool always_current_p (tree name) const;
851 : private:
852 : unsigned temporal_value_stored (unsigned ssa) const;
853 : unsigned temporal_value_calc (unsigned ssa) const;
854 : unsigned m_current_time;
855 : vec <struct time_stamp> m_timestamp;
856 : };
857 :
858 : inline
859 29420773 : temporal_cache::temporal_cache ()
860 : {
861 29420773 : m_current_time = 1;
862 29420773 : m_timestamp.create (0);
863 58841546 : m_timestamp.safe_grow_cleared (num_ssa_names + 1);
864 29420773 : }
865 :
866 : inline
867 29420773 : temporal_cache::~temporal_cache ()
868 : {
869 29420773 : m_timestamp.release ();
870 29420773 : }
871 :
872 : // Return the timestamp value for SSA when it was last stored to
873 : // or 0 if there isn't one.
874 :
875 : inline unsigned
876 158689011 : temporal_cache::temporal_value_stored (unsigned ssa) const
877 : {
878 158689011 : if (ssa >= m_timestamp.length ())
879 : return 0;
880 158689011 : return m_timestamp[ssa].stored;
881 : }
882 :
883 : // Return the timestamp value for SSA when it was last calculated
884 : // or 0 if there isn't one.
885 :
886 : inline unsigned
887 222163365 : temporal_cache::temporal_value_calc (unsigned ssa) const
888 : {
889 222163365 : if (ssa >= m_timestamp.length ())
890 : return 0;
891 222163365 : return m_timestamp[ssa].calc;
892 : }
893 :
894 : // Return TRUE if the timestamp for when NAME was calculated is newer
895 : // than the last time any of its dependents were stored. This indicates
896 : // it dos not need to be calculated again.
897 : // Up to 2 dependencies can be checked.
898 :
899 : bool
900 228991266 : temporal_cache::current_p (tree name, tree dep1, tree dep2) const
901 : {
902 228991266 : if (always_current_p (name))
903 : return true;
904 :
905 : // Any non-registered dependencies will have a value of 0 and thus be older.
906 : // Return true if the last time this was calculated is newer than either
907 : // dependent value.
908 222163365 : unsigned ts = temporal_value_calc (SSA_NAME_VERSION (name));
909 340118845 : if (dep1 && ts < temporal_value_stored (SSA_NAME_VERSION (dep1)))
910 : return false;
911 258729149 : if (dep2 && ts < temporal_value_stored (SSA_NAME_VERSION (dep2)))
912 459263 : return false;
913 :
914 : return true;
915 : }
916 :
917 : // This increments the global timer and sets both timestamps for NAME.
918 :
919 : inline void
920 77720711 : temporal_cache::set_timestamp_stored (tree name)
921 : {
922 77720711 : unsigned v = SSA_NAME_VERSION (name);
923 77720711 : if (v >= m_timestamp.length ())
924 0 : m_timestamp.safe_grow_cleared (num_ssa_names + 20);
925 77720711 : m_timestamp[v].stored = ++m_current_time;
926 77720711 : m_timestamp[v].calc = m_current_time;
927 77720711 : }
928 :
929 : // This increments the global timer and sets the calculated timestamp for NAME.
930 :
931 : inline void
932 124206627 : temporal_cache::set_timestamp_calc (tree name)
933 : {
934 124206627 : unsigned v = SSA_NAME_VERSION (name);
935 124206627 : if (v >= m_timestamp.length ())
936 0 : m_timestamp.safe_grow_cleared (num_ssa_names + 20);
937 124206627 : m_timestamp[v].calc = ++m_current_time;
938 124206627 : }
939 :
940 : // Set the calculated timestamp to 0, marking it as "always up to date".
941 :
942 : inline void
943 136734691 : temporal_cache::set_always_current (tree name)
944 : {
945 136734691 : unsigned v = SSA_NAME_VERSION (name);
946 136734691 : if (v >= m_timestamp.length ())
947 1354 : m_timestamp.safe_grow_cleared (num_ssa_names + 20);
948 : // If stored timestamp hasn't been set, set it now.
949 136734691 : if (m_timestamp[v].stored == 0)
950 129892116 : m_timestamp[v].stored = ++m_current_time;
951 136734691 : m_timestamp[v].calc = 0;
952 136734691 : }
953 :
954 : // Return true if NAME is always current.
955 :
956 : inline bool
957 228991266 : temporal_cache::always_current_p (tree name) const
958 : {
959 228991266 : unsigned v = SSA_NAME_VERSION (name);
960 228991266 : if (v >= m_timestamp.length ())
961 : return false;
962 228991266 : return m_timestamp[v].calc == 0;
963 : }
964 :
965 : // --------------------------------------------------------------------------
966 :
967 : // This class provides an abstraction of a list of blocks to be updated
968 : // by the cache. It is currently a stack but could be changed. It also
969 : // maintains a list of blocks which have failed propagation, and does not
970 : // enter any of those blocks into the list.
971 :
972 : // A vector over the BBs is maintained, and an entry of 0 means it is not in
973 : // a list. Otherwise, the entry is the next block in the list. -1 terminates
974 : // the list. m_head points to the top of the list, -1 if the list is empty.
975 :
976 : class update_list
977 : {
978 : public:
979 : update_list ();
980 : ~update_list ();
981 : void add (basic_block bb);
982 : basic_block pop ();
983 158069017 : inline bool empty_p () { return m_update_head == -1; }
984 5981587 : inline void clear_failures () { bitmap_clear (m_propfail); }
985 3 : inline void propagation_failed (basic_block bb)
986 3 : { bitmap_set_bit (m_propfail, bb->index); }
987 : private:
988 : vec<int> m_update_list;
989 : int m_update_head;
990 : bitmap m_propfail;
991 : bitmap_obstack m_bitmaps;
992 : };
993 :
994 : // Create an update list.
995 :
996 29420773 : update_list::update_list ()
997 : {
998 29420773 : m_update_list.create (0);
999 29420773 : m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun) + 64);
1000 29420773 : m_update_head = -1;
1001 29420773 : bitmap_obstack_initialize (&m_bitmaps);
1002 29420773 : m_propfail = BITMAP_ALLOC (&m_bitmaps);
1003 29420773 : }
1004 :
1005 : // Destroy an update list.
1006 :
1007 29420773 : update_list::~update_list ()
1008 : {
1009 29420773 : m_update_list.release ();
1010 29420773 : bitmap_obstack_release (&m_bitmaps);
1011 29420773 : }
1012 :
1013 : // Add BB to the list of blocks to update, unless it's already in the list.
1014 :
1015 : void
1016 13493054 : update_list::add (basic_block bb)
1017 : {
1018 13493054 : int i = bb->index;
1019 : // If propagation has failed for BB, or its already in the list, don't
1020 : // add it again.
1021 13493054 : if ((unsigned)i >= m_update_list.length ())
1022 74 : m_update_list.safe_grow_cleared (i + 64);
1023 13493054 : if (!m_update_list[i] && !bitmap_bit_p (m_propfail, i))
1024 : {
1025 12790280 : if (empty_p ())
1026 : {
1027 7349264 : m_update_head = i;
1028 7349264 : m_update_list[i] = -1;
1029 : }
1030 : else
1031 : {
1032 5441016 : gcc_checking_assert (m_update_head > 0);
1033 5441016 : m_update_list[i] = m_update_head;
1034 5441016 : m_update_head = i;
1035 : }
1036 : }
1037 13493054 : }
1038 :
1039 : // Remove a block from the list.
1040 :
1041 : basic_block
1042 12790280 : update_list::pop ()
1043 : {
1044 12790280 : gcc_checking_assert (!empty_p ());
1045 12790280 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, m_update_head);
1046 12790280 : int pop = m_update_head;
1047 12790280 : m_update_head = m_update_list[pop];
1048 12790280 : m_update_list[pop] = 0;
1049 12790280 : return bb;
1050 : }
1051 :
1052 : // --------------------------------------------------------------------------
1053 :
1054 29420773 : ranger_cache::ranger_cache (int not_executable_flag, bool use_imm_uses)
1055 : {
1056 29420773 : m_workback = vNULL;
1057 29420773 : m_temporal = new temporal_cache;
1058 :
1059 : // If DOM info is available, spawn an oracle as well.
1060 29420773 : create_relation_oracle ();
1061 : // Create an infer oracle using this cache as the range query. The cache
1062 : // version acts as a read-only query, and will spawn no additional lookups.
1063 : // It just ues what is already known.
1064 29420773 : create_infer_oracle (this, use_imm_uses);
1065 29420773 : create_gori (not_executable_flag, param_vrp_switch_limit);
1066 :
1067 29420773 : unsigned x, lim = last_basic_block_for_fn (cfun);
1068 : // Calculate outgoing range info upfront. This will fully populate the
1069 : // m_maybe_variant bitmap which will help eliminate processing of names
1070 : // which never have their ranges adjusted.
1071 378678949 : for (x = 0; x < lim ; x++)
1072 : {
1073 349258176 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, x);
1074 349258176 : if (bb)
1075 330161669 : gori_ssa ()->exports (bb);
1076 : }
1077 29420773 : m_update = new update_list ();
1078 29420773 : m_stale = BITMAP_ALLOC (NULL);
1079 29420773 : }
1080 :
1081 29420773 : ranger_cache::~ranger_cache ()
1082 : {
1083 29420773 : BITMAP_FREE (m_stale);
1084 29420773 : delete m_update;
1085 29420773 : destroy_infer_oracle ();
1086 29420773 : destroy_relation_oracle ();
1087 58841546 : delete m_temporal;
1088 29420773 : m_workback.release ();
1089 29420773 : }
1090 :
1091 : // Dump the global caches to file F. if GORI_DUMP is true, dump the
1092 : // gori map as well.
1093 :
1094 : void
1095 48 : ranger_cache::dump (FILE *f)
1096 : {
1097 48 : fprintf (f, "Non-varying global ranges:\n");
1098 48 : fprintf (f, "=========================:\n");
1099 48 : m_globals.dump (f);
1100 48 : fprintf (f, "\n");
1101 48 : }
1102 :
1103 : // Dump the caches for basic block BB to file F.
1104 :
1105 : void
1106 257 : ranger_cache::dump_bb (FILE *f, basic_block bb)
1107 : {
1108 257 : gori_ssa ()->dump (f, bb, false);
1109 257 : m_on_entry.dump (f, bb);
1110 257 : m_relation->dump (f, bb);
1111 257 : }
1112 :
1113 : // Get the global range for NAME, and return in R. Return false if the
1114 : // global range is not set, and return the legacy global value in R.
1115 :
1116 : bool
1117 864339829 : ranger_cache::get_global_range (vrange &r, tree name) const
1118 : {
1119 864339829 : if (m_globals.get_range (r, name))
1120 : return true;
1121 199648175 : gimple_range_global (r, name);
1122 199648175 : return false;
1123 : }
1124 :
1125 : // Mark NAME as stale. The next query of NAME forces a recalculation.
1126 :
1127 : void
1128 12958997 : ranger_cache::mark_stale (tree name)
1129 : {
1130 12958997 : if (SSA_NAME_IS_DEFAULT_DEF (name))
1131 : {
1132 : // Default defs have no DEF to recalculate, just create a new timestamp.
1133 1616856 : m_temporal->set_timestamp_stored (name);
1134 : }
1135 11342141 : else if (m_globals.has_range (name))
1136 : {
1137 : // Otherwise Only mark it as stale if it has been processed. If it has no
1138 : // range it will be calculated at the next request anyway.
1139 8332165 : bitmap_set_bit (m_stale, SSA_NAME_VERSION (name));
1140 : }
1141 12958997 : }
1142 :
1143 : // Get the global range for NAME, and return in R. Return false if the
1144 : // global range is not set, and R will contain the legacy global value.
1145 : // CURRENT_P is set to true if the value was in cache and not stale.
1146 : // Otherwise, set CURRENT_P to false and mark as it always current.
1147 : // If the global cache did not have a value, initialize it as well.
1148 : // After this call, the global cache will have a value.
1149 :
1150 : bool
1151 359118085 : ranger_cache::get_global_range (vrange &r, tree name, bool ¤t_p)
1152 : {
1153 359118085 : bool had_global = get_global_range (r, name);
1154 :
1155 : // If there was a global value, set current flag, otherwise set a value.
1156 359118085 : current_p = false;
1157 359118085 : if (had_global)
1158 458440856 : current_p = r.singleton_p ()
1159 458211694 : || m_temporal->current_p (name, gori_ssa ()->depend1 (name),
1160 228991266 : gori_ssa ()->depend2 (name));
1161 : else
1162 : {
1163 : // If no global value has been set and value is VARYING, fold the stmt
1164 : // using just global ranges to get a better initial value.
1165 : // After inlining we tend to decide some things are constant, so
1166 : // so not do this evaluation after inlining.
1167 129897657 : if (r.varying_p () && !cfun->after_inlining)
1168 : {
1169 21220642 : gimple *s = SSA_NAME_DEF_STMT (name);
1170 : // Do not process PHIs as SCEV may be in use and it can
1171 : // spawn cyclic lookups.
1172 21220642 : if (gimple_get_lhs (s) == name && !is_a<gphi *> (s))
1173 : {
1174 16608306 : if (!fold_range (r, s, get_global_range_query ()))
1175 0 : gimple_range_global (r, name);
1176 : }
1177 : }
1178 129897657 : m_globals.set_range (name, r);
1179 : }
1180 :
1181 : // If NAME is out of date, clear the bit and mark as not current.
1182 359118085 : if (bitmap_bit_p (m_stale, SSA_NAME_VERSION (name)))
1183 : {
1184 2251588 : bitmap_clear_bit (m_stale, SSA_NAME_VERSION (name));
1185 2251588 : current_p = false;
1186 : }
1187 :
1188 : // If the existing value was not current, mark it as always current.
1189 359118085 : if (!current_p)
1190 136734691 : m_temporal->set_always_current (name);
1191 359118085 : return had_global;
1192 : }
1193 :
1194 : // Consumers of NAME that have already calculated values should recalculate.
1195 : // Accomplished by updating the timestamp.
1196 :
1197 : void
1198 63196828 : ranger_cache::update_consumers (tree name)
1199 : {
1200 63196828 : m_temporal->set_timestamp_stored (name);
1201 63196828 : }
1202 :
1203 : // Set the global range of NAME to R and give it a timestamp.
1204 :
1205 : void
1206 137113654 : ranger_cache::set_global_range (tree name, const vrange &r, bool changed)
1207 : {
1208 137113654 : if (!changed)
1209 : {
1210 : // If the value did not change, simply update the calculated timestamp.
1211 124206627 : m_temporal->set_timestamp_calc (name);
1212 124206627 : return;
1213 : }
1214 12907027 : if (m_globals.set_range (name, r))
1215 : {
1216 : // If there was already a range set, propagate the new value.
1217 12850661 : basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1218 12850661 : if (!bb)
1219 1536 : bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1220 :
1221 12850661 : if (DEBUG_RANGE_CACHE)
1222 0 : fprintf (dump_file, " GLOBAL :");
1223 :
1224 12850661 : propagate_updated_value (name, bb);
1225 : }
1226 : // Constants no longer need to tracked. Any further refinement has to be
1227 : // undefined. Propagation works better with constants. PR 100512.
1228 : // Pointers which resolve to non-zero also do not need
1229 : // tracking in the cache as they will never change. See PR 98866.
1230 : // Timestamp must always be updated, or dependent calculations may
1231 : // not include this latest value. PR 100774.
1232 :
1233 : // With Points_to info in prange now, it is no longer acceptable to make
1234 : // [1, +INF] invariant, as most points to values will have that range,
1235 : // and then we lose the ability to propagate points to info.
1236 :
1237 12907027 : if (r.singleton_p ())
1238 881403 : gori_ssa ()->set_range_invariant (name);
1239 :
1240 : // update the stored and calucalted timestamp now.
1241 12907027 : m_temporal->set_timestamp_stored (name);
1242 : }
1243 :
1244 : // Provide lookup for the gori-computes class to access the best known range
1245 : // of an ssa_name in any given basic block. Note, this does no additional
1246 : // lookups, just accesses the data that is already known.
1247 :
1248 : // Get the range of NAME when the def occurs in block BB. If BB is NULL
1249 : // get the best global value available.
1250 :
1251 : void
1252 220649005 : ranger_cache::range_of_def (vrange &r, tree name, basic_block bb)
1253 : {
1254 220649005 : gcc_checking_assert (gimple_range_ssa_p (name));
1255 369588276 : gcc_checking_assert (!bb || bb == gimple_bb (SSA_NAME_DEF_STMT (name)));
1256 :
1257 : // Pick up the best global range available.
1258 220649005 : if (!m_globals.get_range (r, name))
1259 : {
1260 : // If that fails, try to calculate the range using just global values.
1261 30813939 : gimple *s = SSA_NAME_DEF_STMT (name);
1262 30813939 : if (gimple_get_lhs (s) == name)
1263 27365288 : fold_range (r, s, get_global_range_query ());
1264 : else
1265 3448651 : gimple_range_global (r, name);
1266 : }
1267 220649005 : }
1268 :
1269 : // Get the range of NAME as it occurs on entry to block BB. Use MODE for
1270 : // lookups.
1271 :
1272 : void
1273 159798013 : ranger_cache::entry_range (vrange &r, tree name, basic_block bb,
1274 : enum rfd_mode mode)
1275 : {
1276 159798013 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1277 : {
1278 0 : gimple_range_global (r, name);
1279 0 : return;
1280 : }
1281 :
1282 : // If NAME is invariant, simply return the defining range.
1283 159798013 : if (!gori ().has_edge_range_p (name))
1284 : {
1285 33430630 : range_of_def (r, name);
1286 33430630 : return;
1287 : }
1288 :
1289 : // Look for the on-entry value of name in BB from the cache.
1290 : // Otherwise pick up the best available global value.
1291 126367383 : if (!m_on_entry.get_bb_range (r, name, bb))
1292 45040802 : if (!range_from_dom (r, name, bb, mode))
1293 38279104 : range_of_def (r, name);
1294 : }
1295 :
1296 : // Get the range of NAME as it occurs on exit from block BB. Use MODE for
1297 : // lookups.
1298 :
1299 : void
1300 111353735 : ranger_cache::exit_range (vrange &r, tree name, basic_block bb,
1301 : enum rfd_mode mode)
1302 : {
1303 111353735 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1304 : {
1305 61908 : gimple_range_global (r, name);
1306 61908 : return;
1307 : }
1308 :
1309 111291827 : gimple *s = SSA_NAME_DEF_STMT (name);
1310 111291827 : basic_block def_bb = gimple_bb (s);
1311 111291827 : if (def_bb == bb)
1312 45471077 : range_of_def (r, name, bb);
1313 : else
1314 65820750 : entry_range (r, name, bb, mode);
1315 : }
1316 :
1317 : // Get the range of NAME on edge E using MODE, return the result in R.
1318 : // Always returns a range and true.
1319 :
1320 : bool
1321 100756824 : ranger_cache::edge_range (vrange &r, edge e, tree name, enum rfd_mode mode)
1322 : {
1323 100756824 : exit_range (r, name, e->src, mode);
1324 : // If this is not an abnormal edge, check for inferred ranges on exit.
1325 100756824 : if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
1326 100427225 : infer_oracle ().maybe_adjust_range (r, name, e->src);
1327 100756824 : value_range er (TREE_TYPE (name));
1328 100756824 : if (gori ().edge_range_p (er, e, name, *this))
1329 23450447 : r.intersect (er);
1330 201513648 : return true;
1331 100756824 : }
1332 :
1333 :
1334 :
1335 : // Implement range_of_expr.
1336 :
1337 : bool
1338 240145542 : ranger_cache::range_of_expr (vrange &r, tree name, gimple *stmt)
1339 : {
1340 240145542 : if (!gimple_range_ssa_p (name))
1341 42700009 : get_tree_range (r, name, stmt);
1342 : /* If no context is provided, pick up the global value. */
1343 197445533 : else if (!stmt)
1344 76 : get_global_range (r, name);
1345 : else
1346 : {
1347 197445457 : basic_block bb = gimple_bb (stmt);
1348 197445457 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1349 197445457 : basic_block def_bb = gimple_bb (def_stmt);
1350 :
1351 197445457 : if (bb == def_bb)
1352 103468194 : range_of_def (r, name, bb);
1353 : else
1354 93977263 : entry_range (r, name, bb, RFD_NONE);
1355 : }
1356 240145542 : return true;
1357 : }
1358 :
1359 :
1360 : // Implement range_on_edge. Always return the best available range using
1361 : // the current cache values.
1362 :
1363 : bool
1364 75207054 : ranger_cache::range_on_edge (vrange &r, edge e, tree expr)
1365 : {
1366 75207054 : if (gimple_range_ssa_p (expr))
1367 72113154 : return edge_range (r, e, expr, RFD_NONE);
1368 3093900 : return get_tree_range (r, expr, NULL);
1369 : }
1370 :
1371 : // Return a static range for NAME on entry to basic block BB in R. If
1372 : // calc is true, fill any cache entries required between BB and the
1373 : // def block for NAME. Otherwise, return false if the cache is empty.
1374 :
1375 : bool
1376 410175511 : ranger_cache::block_range (vrange &r, basic_block bb, tree name, bool calc)
1377 : {
1378 410175511 : gcc_checking_assert (gimple_range_ssa_p (name));
1379 :
1380 : // If there are no range calculations anywhere in the IL, global range
1381 : // applies everywhere, so don't bother caching it.
1382 410175511 : if (!gori ().has_edge_range_p (name))
1383 : return false;
1384 :
1385 259732471 : if (calc)
1386 : {
1387 127861277 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1388 127861277 : basic_block def_bb = NULL;
1389 127861277 : if (def_stmt)
1390 127861277 : def_bb = gimple_bb (def_stmt);
1391 127861277 : if (!def_bb)
1392 : {
1393 : // If we get to the entry block, this better be a default def
1394 : // or range_on_entry was called for a block not dominated by
1395 : // the def. But it could be also SSA_NAME defined by a statement
1396 : // not yet in the IL (such as queued edge insertion), in that case
1397 : // just punt.
1398 16765736 : if (!SSA_NAME_IS_DEFAULT_DEF (name))
1399 : return false;
1400 16765735 : def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1401 : }
1402 :
1403 : // There is no range on entry for the definition block.
1404 127861276 : if (def_bb == bb)
1405 : return false;
1406 :
1407 : // Otherwise, go figure out what is known in predecessor blocks.
1408 127861269 : fill_block_cache (name, bb, def_bb);
1409 127861269 : gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
1410 : }
1411 259732463 : return m_on_entry.get_bb_range (r, name, bb);
1412 : }
1413 :
1414 : // If there is anything in the propagation update_list, continue
1415 : // processing NAME until the list of blocks is empty.
1416 :
1417 : void
1418 5981587 : ranger_cache::propagate_cache (tree name)
1419 : {
1420 5981587 : basic_block bb;
1421 5981587 : edge_iterator ei;
1422 5981587 : edge e;
1423 5981587 : tree type = TREE_TYPE (name);
1424 5981587 : value_range new_range (type);
1425 5981587 : value_range current_range (type);
1426 5981587 : value_range e_range (type);
1427 :
1428 : // Process each block by seeing if its calculated range on entry is
1429 : // the same as its cached value. If there is a difference, update
1430 : // the cache to reflect the new value, and check to see if any
1431 : // successors have cache entries which may need to be checked for
1432 : // updates.
1433 :
1434 24753454 : while (!m_update->empty_p ())
1435 : {
1436 12790280 : bb = m_update->pop ();
1437 12790280 : gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
1438 12790280 : m_on_entry.get_bb_range (current_range, name, bb);
1439 :
1440 12790280 : if (DEBUG_RANGE_CACHE)
1441 : {
1442 0 : fprintf (dump_file, "FWD visiting block %d for ", bb->index);
1443 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1444 0 : fprintf (dump_file, " starting range : ");
1445 0 : current_range.dump (dump_file);
1446 0 : fprintf (dump_file, "\n");
1447 : }
1448 :
1449 : // Calculate the "new" range on entry by unioning the pred edges.
1450 12790280 : new_range.set_undefined ();
1451 27257283 : FOR_EACH_EDGE (e, ei, bb->preds)
1452 : {
1453 17926875 : edge_range (e_range, e, name, RFD_READ_ONLY);
1454 17926875 : if (DEBUG_RANGE_CACHE)
1455 : {
1456 0 : fprintf (dump_file, " edge %d->%d :", e->src->index, bb->index);
1457 0 : e_range.dump (dump_file);
1458 0 : fprintf (dump_file, "\n");
1459 : }
1460 17926875 : new_range.union_ (e_range);
1461 17926875 : if (new_range.varying_p ())
1462 : break;
1463 : }
1464 :
1465 : // If the range on entry has changed, update it.
1466 12790280 : if (new_range != current_range)
1467 : {
1468 7299347 : bool ok_p = m_on_entry.set_bb_range (name, bb, new_range);
1469 : // If the cache couldn't set the value, mark it as failed.
1470 7299347 : if (!ok_p)
1471 3 : m_update->propagation_failed (bb);
1472 7299347 : if (DEBUG_RANGE_CACHE)
1473 : {
1474 0 : if (!ok_p)
1475 : {
1476 0 : fprintf (dump_file, " Cache failure to store value:");
1477 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1478 0 : fprintf (dump_file, " ");
1479 : }
1480 : else
1481 : {
1482 0 : fprintf (dump_file, " Updating range to ");
1483 0 : new_range.dump (dump_file);
1484 : }
1485 0 : fprintf (dump_file, "\n Updating blocks :");
1486 : }
1487 : // Mark each successor that has a range to re-check its range
1488 18754147 : FOR_EACH_EDGE (e, ei, bb->succs)
1489 11454800 : if (m_on_entry.bb_range_p (name, e->dest))
1490 : {
1491 6897094 : if (DEBUG_RANGE_CACHE)
1492 0 : fprintf (dump_file, " bb%d",e->dest->index);
1493 6897094 : m_update->add (e->dest);
1494 : }
1495 7299347 : if (DEBUG_RANGE_CACHE)
1496 0 : fprintf (dump_file, "\n");
1497 : }
1498 : }
1499 5981587 : if (DEBUG_RANGE_CACHE)
1500 : {
1501 0 : fprintf (dump_file, "DONE visiting blocks for ");
1502 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1503 0 : fprintf (dump_file, "\n");
1504 : }
1505 5981587 : m_update->clear_failures ();
1506 5981587 : }
1507 :
1508 : // Check to see if an update to the value for NAME in BB has any effect
1509 : // on values already in the on-entry cache for successor blocks.
1510 : // If it does, update them. Don't visit any blocks which don't have a cache
1511 : // entry.
1512 :
1513 : void
1514 56385398 : ranger_cache::propagate_updated_value (tree name, basic_block bb)
1515 : {
1516 56385398 : edge e;
1517 56385398 : edge_iterator ei;
1518 :
1519 : // The update work list should be empty at this point.
1520 56385398 : gcc_checking_assert (m_update->empty_p ());
1521 56385398 : gcc_checking_assert (bb);
1522 :
1523 56385398 : if (DEBUG_RANGE_CACHE)
1524 : {
1525 0 : fprintf (dump_file, " UPDATE cache for ");
1526 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1527 0 : fprintf (dump_file, " in BB %d : successors : ", bb->index);
1528 : }
1529 163628557 : FOR_EACH_EDGE (e, ei, bb->succs)
1530 : {
1531 : // Only update active cache entries.
1532 107243159 : if (m_on_entry.bb_range_p (name, e->dest))
1533 : {
1534 5108928 : m_update->add (e->dest);
1535 5108928 : if (DEBUG_RANGE_CACHE)
1536 0 : fprintf (dump_file, " UPDATE: bb%d", e->dest->index);
1537 : }
1538 : }
1539 56385398 : if (!m_update->empty_p ())
1540 : {
1541 5035793 : if (DEBUG_RANGE_CACHE)
1542 0 : fprintf (dump_file, "\n");
1543 5035793 : propagate_cache (name);
1544 : }
1545 : else
1546 : {
1547 51349605 : if (DEBUG_RANGE_CACHE)
1548 0 : fprintf (dump_file, " : No updates!\n");
1549 : }
1550 56385398 : }
1551 :
1552 : // Make sure that the range-on-entry cache for NAME is set for block BB.
1553 : // Work back through the CFG to DEF_BB ensuring the range is calculated
1554 : // on the block/edges leading back to that point.
1555 :
1556 : void
1557 127861269 : ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
1558 : {
1559 127861269 : edge_iterator ei;
1560 127861269 : edge e;
1561 127861269 : tree type = TREE_TYPE (name);
1562 127861269 : value_range block_result (type);
1563 127861269 : value_range undefined (type);
1564 :
1565 : // At this point we shouldn't be looking at the def, entry block.
1566 127861269 : gcc_checking_assert (bb != def_bb && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
1567 127861269 : unsigned start_length = m_workback.length ();
1568 :
1569 : // If the block cache is set, then we've already visited this block.
1570 127861269 : if (m_on_entry.bb_range_p (name, bb))
1571 : return;
1572 :
1573 54458673 : if (DEBUG_RANGE_CACHE)
1574 : {
1575 0 : fprintf (dump_file, "\n");
1576 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1577 0 : fprintf (dump_file, " : ");
1578 : }
1579 :
1580 : // Check if a dominators can supply the range.
1581 54458673 : if (range_from_dom (block_result, name, bb, RFD_FILL))
1582 : {
1583 53512879 : if (DEBUG_RANGE_CACHE)
1584 : {
1585 0 : fprintf (dump_file, "Filled from dominator! : ");
1586 0 : block_result.dump (dump_file);
1587 0 : fprintf (dump_file, "\n");
1588 : }
1589 : // See if any equivalences can refine it.
1590 : // PR 109462, like 108139 below, a one way equivalence introduced
1591 : // by a PHI node can also be through the definition side. Disallow it.
1592 53512879 : tree equiv_name;
1593 53512879 : relation_kind rel;
1594 53512879 : int prec = TYPE_PRECISION (type);
1595 : // If there are too many basic blocks, do not attempt to process
1596 : // equivalencies.
1597 53512879 : if (last_basic_block_for_fn (cfun) > param_vrp_sparse_threshold)
1598 : {
1599 420741 : m_on_entry.set_bb_range (name, bb, block_result);
1600 841450 : gcc_checking_assert (m_workback.length () == start_length);
1601 : return;
1602 : }
1603 63212479 : FOR_EACH_PARTIAL_AND_FULL_EQUIV (m_relation, bb, name, equiv_name, rel)
1604 : {
1605 10120341 : basic_block equiv_bb = gimple_bb (SSA_NAME_DEF_STMT (equiv_name));
1606 :
1607 : // Ignore partial equivs that are smaller than this object.
1608 17941711 : if (rel != VREL_EQ && prec > pe_to_bits (rel))
1609 3749757 : continue;
1610 :
1611 : // Check if the equiv has any ranges calculated.
1612 9046660 : if (!gori ().has_edge_range_p (equiv_name))
1613 388632 : continue;
1614 :
1615 : // Check if the equiv definition dominates this block
1616 8658028 : if (equiv_bb == bb ||
1617 8432211 : (equiv_bb && !dominated_by_p (CDI_DOMINATORS, bb, equiv_bb)))
1618 2287444 : continue;
1619 :
1620 6370584 : if (DEBUG_RANGE_CACHE)
1621 : {
1622 0 : if (rel == VREL_EQ)
1623 0 : fprintf (dump_file, "Checking Equivalence (");
1624 : else
1625 0 : fprintf (dump_file, "Checking Partial equiv (");
1626 0 : print_relation (dump_file, rel);
1627 0 : fprintf (dump_file, ") ");
1628 0 : print_generic_expr (dump_file, equiv_name, TDF_SLIM);
1629 0 : fprintf (dump_file, "\n");
1630 : }
1631 6370584 : value_range equiv_range (TREE_TYPE (equiv_name));
1632 6370584 : if (range_from_dom (equiv_range, equiv_name, bb, RFD_READ_ONLY))
1633 : {
1634 6370584 : if (rel != VREL_EQ)
1635 4351979 : range_cast (equiv_range, type);
1636 : else
1637 2018605 : adjust_equivalence_range (equiv_range);
1638 :
1639 6370584 : if (block_result.intersect (equiv_range))
1640 : {
1641 352456 : if (DEBUG_RANGE_CACHE)
1642 : {
1643 0 : if (rel == VREL_EQ)
1644 0 : fprintf (dump_file, "Equivalence update! : ");
1645 : else
1646 0 : fprintf (dump_file, "Partial equiv update! : ");
1647 0 : print_generic_expr (dump_file, equiv_name, TDF_SLIM);
1648 0 : fprintf (dump_file, " has range : ");
1649 0 : equiv_range.dump (dump_file);
1650 0 : fprintf (dump_file, " refining range to :");
1651 0 : block_result.dump (dump_file);
1652 0 : fprintf (dump_file, "\n");
1653 : }
1654 : }
1655 : }
1656 6370584 : }
1657 :
1658 53092138 : m_on_entry.set_bb_range (name, bb, block_result);
1659 103500083 : gcc_checking_assert (m_workback.length () == start_length);
1660 : return;
1661 : }
1662 :
1663 : // Visit each block back to the DEF. Initialize each one to UNDEFINED.
1664 : // m_visited at the end will contain all the blocks that we needed to set
1665 : // the range_on_entry cache for.
1666 945794 : m_workback.safe_push (bb);
1667 945794 : undefined.set_undefined ();
1668 945794 : m_on_entry.set_bb_range (name, bb, undefined);
1669 945794 : gcc_checking_assert (m_update->empty_p ());
1670 :
1671 6223093 : while (m_workback.length () > start_length)
1672 : {
1673 5277299 : basic_block node = m_workback.pop ();
1674 5277299 : if (DEBUG_RANGE_CACHE)
1675 : {
1676 0 : fprintf (dump_file, "BACK visiting block %d for ", node->index);
1677 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1678 0 : fprintf (dump_file, "\n");
1679 : }
1680 :
1681 12615906 : FOR_EACH_EDGE (e, ei, node->preds)
1682 : {
1683 7338607 : basic_block pred = e->src;
1684 7338607 : value_range r (TREE_TYPE (name));
1685 :
1686 7338607 : if (DEBUG_RANGE_CACHE)
1687 0 : fprintf (dump_file, " %d->%d ",e->src->index, e->dest->index);
1688 :
1689 : // If the pred block is the def block add this BB to update list.
1690 7338607 : if (pred == def_bb)
1691 : {
1692 887124 : m_update->add (node);
1693 887124 : continue;
1694 : }
1695 :
1696 : // If the pred is entry but NOT def, then it is used before
1697 : // defined, it'll get set to [] and no need to update it.
1698 6451483 : if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1699 : {
1700 333 : if (DEBUG_RANGE_CACHE)
1701 0 : fprintf (dump_file, "entry: bail.");
1702 333 : continue;
1703 : }
1704 :
1705 : // Regardless of whether we have visited pred or not, if the
1706 : // pred has inferred ranges, revisit this block.
1707 : // Don't search the DOM tree.
1708 6451150 : if (infer_oracle ().has_range_p (pred, name))
1709 : {
1710 13338 : if (DEBUG_RANGE_CACHE)
1711 0 : fprintf (dump_file, "Inferred range: update ");
1712 13338 : m_update->add (node);
1713 : }
1714 :
1715 : // If the pred block already has a range, or if it can contribute
1716 : // something new. Ie, the edge generates a range of some sort.
1717 6451150 : if (m_on_entry.get_bb_range (r, name, pred))
1718 : {
1719 2119645 : if (DEBUG_RANGE_CACHE)
1720 : {
1721 0 : fprintf (dump_file, "has cache, ");
1722 0 : r.dump (dump_file);
1723 0 : fprintf (dump_file, ", ");
1724 : }
1725 2119645 : if (!r.undefined_p () || gori ().has_edge_range_p (name, e))
1726 : {
1727 586570 : m_update->add (node);
1728 586570 : if (DEBUG_RANGE_CACHE)
1729 0 : fprintf (dump_file, "update. ");
1730 : }
1731 2119645 : continue;
1732 : }
1733 :
1734 4331505 : if (DEBUG_RANGE_CACHE)
1735 0 : fprintf (dump_file, "pushing undefined pred block.\n");
1736 : // If the pred hasn't been visited (has no range), add it to
1737 : // the list.
1738 4331505 : gcc_checking_assert (!m_on_entry.bb_range_p (name, pred));
1739 4331505 : m_on_entry.set_bb_range (name, pred, undefined);
1740 4331505 : m_workback.safe_push (pred);
1741 7338607 : }
1742 : }
1743 :
1744 945794 : if (DEBUG_RANGE_CACHE)
1745 0 : fprintf (dump_file, "\n");
1746 :
1747 : // Now fill in the marked blocks with values.
1748 945794 : propagate_cache (name);
1749 945794 : if (DEBUG_RANGE_CACHE)
1750 0 : fprintf (dump_file, " Propagation update done.\n");
1751 127861269 : }
1752 :
1753 : // Resolve the range of BB if the dominators range is R by calculating incoming
1754 : // edges to this block. All lead back to the dominator so should be cheap.
1755 : // The range for BB is set and returned in R.
1756 :
1757 : void
1758 4547187 : ranger_cache::resolve_dom (vrange &r, tree name, basic_block bb)
1759 : {
1760 4547187 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1761 4547187 : basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1762 :
1763 : // if it doesn't already have a value, store the incoming range.
1764 4547187 : if (!m_on_entry.bb_range_p (name, dom_bb) && def_bb != dom_bb)
1765 : {
1766 : // If the range can't be store, don't try to accumulate
1767 : // the range in PREV_BB due to excessive recalculations.
1768 1221917 : if (!m_on_entry.set_bb_range (name, dom_bb, r))
1769 0 : return;
1770 : }
1771 : // With the dominator set, we should be able to cheaply query
1772 : // each incoming edge now and accumulate the results.
1773 4547187 : r.set_undefined ();
1774 4547187 : edge e;
1775 4547187 : edge_iterator ei;
1776 4547187 : value_range er (TREE_TYPE (name));
1777 15288106 : FOR_EACH_EDGE (e, ei, bb->preds)
1778 : {
1779 : // If the predecessor is dominated by this block, then there is a back
1780 : // edge, and won't provide anything useful. We'll actually end up with
1781 : // VARYING as we will not resolve this node.
1782 10740919 : if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1783 24124 : continue;
1784 10716795 : edge_range (er, e, name, RFD_READ_ONLY);
1785 10716795 : r.union_ (er);
1786 : }
1787 : // Set the cache in PREV_BB so it is not calculated again.
1788 4547187 : m_on_entry.set_bb_range (name, bb, r);
1789 4547187 : }
1790 :
1791 : // Get the range of NAME from dominators of BB and return it in R. Search the
1792 : // dominator tree based on MODE.
1793 :
1794 : bool
1795 105870059 : ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
1796 : enum rfd_mode mode)
1797 : {
1798 105870059 : if (mode == RFD_NONE || !dom_info_available_p (CDI_DOMINATORS))
1799 : return false;
1800 :
1801 : // Search back to the definition block or entry block.
1802 66645161 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1803 66645161 : if (def_bb == NULL)
1804 8284784 : def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1805 :
1806 66645161 : basic_block bb;
1807 66645161 : basic_block prev_bb = start_bb;
1808 :
1809 : // Track any inferred ranges seen.
1810 66645161 : value_range infer (TREE_TYPE (name));
1811 66645161 : infer.set_varying (TREE_TYPE (name));
1812 :
1813 : // Range on entry to the DEF block should not be queried.
1814 66645161 : gcc_checking_assert (start_bb != def_bb);
1815 66645161 : unsigned start_limit = m_workback.length ();
1816 :
1817 : // Default value is global range.
1818 66645161 : get_global_range (r, name);
1819 :
1820 : // The dominator of EXIT_BLOCK doesn't seem to be set, so at least handle
1821 : // the common single exit cases.
1822 66798621 : if (start_bb == EXIT_BLOCK_PTR_FOR_FN (cfun) && single_pred_p (start_bb))
1823 153211 : bb = single_pred_edge (start_bb)->src;
1824 : else
1825 66491950 : bb = get_immediate_dominator (CDI_DOMINATORS, start_bb);
1826 :
1827 66645161 : bool abnormal_dominator = false;
1828 : // Search until a value is found, pushing blocks which may need calculating.
1829 432549802 : for ( ; bb; prev_bb = bb, bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1830 : {
1831 431696408 : if (has_abnormal_call_or_eh_pred_edge_p (prev_bb))
1832 : abnormal_dominator = true;
1833 :
1834 : // find the taken outgoing edge and check if it is abnormal.
1835 431456402 : if (!abnormal_dominator)
1836 : {
1837 429709059 : edge e;
1838 429709059 : edge_iterator ei;
1839 657401182 : FOR_EACH_EDGE (e, ei, bb->succs)
1840 641883454 : if (dominated_by_p (CDI_DOMINATORS, prev_bb, e->dest))
1841 : {
1842 414191331 : if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
1843 429709059 : abnormal_dominator = true;
1844 : break;
1845 : }
1846 : // Accumulate any block exit inferred ranges.
1847 429709059 : infer_oracle ().maybe_adjust_range (infer, name, bb);
1848 : }
1849 :
1850 : // This block has an outgoing range.
1851 431696408 : if (gori ().has_edge_range_p (name, bb))
1852 47037156 : m_workback.safe_push (prev_bb);
1853 : else
1854 : {
1855 : // Normally join blocks don't carry any new range information on
1856 : // incoming edges. If the first incoming edge to this block does
1857 : // generate a range, calculate the ranges if all incoming edges
1858 : // are also dominated by the dominator. (Avoids backedges which
1859 : // will break the rule of moving only upward in the dominator tree).
1860 : // If the first pred does not generate a range, then we will be
1861 : // using the dominator range anyway, so that's all the check needed.
1862 384659252 : if (EDGE_COUNT (prev_bb->preds) > 1
1863 384659252 : && gori ().has_edge_range_p (name, EDGE_PRED (prev_bb, 0)->src))
1864 : {
1865 751068 : edge e;
1866 751068 : edge_iterator ei;
1867 751068 : bool all_dom = true;
1868 2545815 : FOR_EACH_EDGE (e, ei, prev_bb->preds)
1869 1794747 : if (e->src != bb
1870 1794747 : && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
1871 : {
1872 : all_dom = false;
1873 : break;
1874 : }
1875 751068 : if (all_dom)
1876 751068 : m_workback.safe_push (prev_bb);
1877 : }
1878 : }
1879 :
1880 431696408 : if (def_bb == bb)
1881 : break;
1882 :
1883 390893087 : if (m_on_entry.get_bb_range (r, name, bb))
1884 : break;
1885 : }
1886 :
1887 66645161 : if (DEBUG_RANGE_CACHE)
1888 : {
1889 0 : fprintf (dump_file, "CACHE: BB %d DOM query for ", start_bb->index);
1890 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1891 0 : fprintf (dump_file, ", found ");
1892 0 : r.dump (dump_file);
1893 0 : if (bb)
1894 0 : fprintf (dump_file, " at BB%d\n", bb->index);
1895 : else
1896 0 : fprintf (dump_file, " at function top\n");
1897 : }
1898 :
1899 : // Now process any blocks wit incoming edges that nay have adjustments.
1900 114433385 : while (m_workback.length () > start_limit)
1901 : {
1902 47788224 : value_range er (TREE_TYPE (name));
1903 47788224 : prev_bb = m_workback.pop ();
1904 47788224 : if (!single_pred_p (prev_bb))
1905 : {
1906 : // Non single pred means we need to cache a value in the dominator
1907 : // so we can cheaply calculate incoming edges to this block, and
1908 : // then store the resulting value. If processing mode is not
1909 : // RFD_FILL, then the cache cant be stored to, so don't try.
1910 : // Otherwise this becomes a quadratic timed calculation.
1911 6815433 : if (mode == RFD_FILL)
1912 4547187 : resolve_dom (r, name, prev_bb);
1913 6815433 : continue;
1914 : }
1915 :
1916 40972791 : edge e = single_pred_edge (prev_bb);
1917 40972791 : bb = e->src;
1918 40972791 : if (gori ().edge_range_p (er, e, name, *this))
1919 : {
1920 37050360 : r.intersect (er);
1921 : // If this is a normal edge, apply any inferred ranges.
1922 37050360 : if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
1923 37050360 : infer_oracle ().maybe_adjust_range (r, name, bb);
1924 :
1925 37050360 : if (DEBUG_RANGE_CACHE)
1926 : {
1927 0 : fprintf (dump_file, "CACHE: Adjusted edge range for %d->%d : ",
1928 : bb->index, prev_bb->index);
1929 0 : r.dump (dump_file);
1930 0 : fprintf (dump_file, "\n");
1931 : }
1932 : }
1933 47788224 : }
1934 :
1935 : // Apply any inferred ranges discovered.
1936 66645161 : r.intersect (infer);
1937 :
1938 66645161 : if (DEBUG_RANGE_CACHE)
1939 : {
1940 0 : fprintf (dump_file, "CACHE: Range for DOM returns : ");
1941 0 : r.dump (dump_file);
1942 0 : fprintf (dump_file, "\n");
1943 : }
1944 66645161 : return true;
1945 66645161 : }
1946 :
1947 : // This routine will register an inferred value in block BB, and possibly
1948 : // update the on-entry cache if appropriate.
1949 :
1950 : void
1951 16878956 : ranger_cache::register_inferred_value (const vrange &ir, tree name,
1952 : basic_block bb)
1953 : {
1954 16878956 : value_range r (TREE_TYPE (name));
1955 16878956 : if (!m_on_entry.get_bb_range (r, name, bb))
1956 10596911 : exit_range (r, name, bb, RFD_READ_ONLY);
1957 16878956 : if (r.intersect (ir))
1958 : {
1959 4930062 : m_on_entry.set_bb_range (name, bb, r);
1960 : // If this range was invariant before, remove invariant.
1961 4930062 : if (!gori ().has_edge_range_p (name))
1962 4114596 : gori_ssa ()->set_range_invariant (name, false);
1963 : }
1964 16878956 : }
1965 :
1966 : // This routine is used during a block walk to adjust any inferred ranges
1967 : // of operands on stmt S.
1968 :
1969 : void
1970 274244584 : ranger_cache::apply_inferred_ranges (gimple *s)
1971 : {
1972 274244584 : bool update = true;
1973 :
1974 274244584 : basic_block bb = gimple_bb (s);
1975 274244584 : gimple_infer_range infer(s, this);
1976 274244584 : if (infer.num () == 0)
1977 : return;
1978 :
1979 : // Do not update the on-entry cache for block ending stmts.
1980 16557859 : if (stmt_ends_bb_p (s))
1981 : {
1982 1185610 : edge_iterator ei;
1983 1185610 : edge e;
1984 2138483 : FOR_EACH_EDGE (e, ei, gimple_bb (s)->succs)
1985 2132672 : if (!(e->flags & (EDGE_ABNORMAL|EDGE_EH)))
1986 : break;
1987 1185610 : if (e == NULL)
1988 5811 : update = false;
1989 : }
1990 :
1991 16557859 : infer_oracle ().add_ranges (s, infer);
1992 16557859 : if (update)
1993 33405297 : for (unsigned x = 0; x < infer.num (); x++)
1994 16853249 : register_inferred_value (infer.range (x), infer.name (x), bb);
1995 16557859 : }
1996 :
1997 : // Reset range info for NAME.
1998 :
1999 : void
2000 1157 : ranger_cache::reset_range_info (tree name)
2001 : {
2002 1157 : m_on_entry.clear (name);
2003 1157 : m_globals.clear_range (name);
2004 1157 : range_query::reset_range_info (name);
2005 1157 : }
|
