Daily bump.
[official-gcc.git] / gcc / gimple-range-cache.cc
blob47e95ec23beb8a0454861eac642c2138c370521d
1 /* Gimple ranger SSA cache implementation.
2 Copyright (C) 2017-2021 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>.
5 This file is part of GCC.
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.
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.
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/>. */
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 "tree-cfg.h"
33 #define DEBUG_RANGE_CACHE (dump_file \
34 && (param_ranger_debug & RANGER_DEBUG_CACHE))
36 // During contructor, allocate the vector of ssa_names.
38 non_null_ref::non_null_ref ()
40 m_nn.create (num_ssa_names);
41 m_nn.quick_grow_cleared (num_ssa_names);
42 bitmap_obstack_initialize (&m_bitmaps);
45 // Free any bitmaps which were allocated,a swell as the vector itself.
47 non_null_ref::~non_null_ref ()
49 bitmap_obstack_release (&m_bitmaps);
50 m_nn.release ();
53 // Return true if NAME has a non-null dereference in block bb. If this is the
54 // first query for NAME, calculate the summary first.
55 // If SEARCH_DOM is true, the search the dominator tree as well.
57 bool
58 non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom)
60 if (!POINTER_TYPE_P (TREE_TYPE (name)))
61 return false;
63 unsigned v = SSA_NAME_VERSION (name);
64 if (v >= m_nn.length ())
65 m_nn.safe_grow_cleared (num_ssa_names + 1);
67 if (!m_nn[v])
68 process_name (name);
70 if (bitmap_bit_p (m_nn[v], bb->index))
71 return true;
73 // See if any dominator has set non-zero.
74 if (search_dom && dom_info_available_p (CDI_DOMINATORS))
76 // Search back to the Def block, or the top, whichever is closer.
77 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
78 basic_block def_dom = def_bb
79 ? get_immediate_dominator (CDI_DOMINATORS, def_bb)
80 : NULL;
81 for ( ;
82 bb && bb != def_dom;
83 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
84 if (bitmap_bit_p (m_nn[v], bb->index))
85 return true;
87 return false;
90 // If NAME has a non-null dereference in block BB, adjust R with the
91 // non-zero information from non_null_deref_p, and return TRUE. If
92 // SEARCH_DOM is true, non_null_deref_p should search the dominator tree.
94 bool
95 non_null_ref::adjust_range (irange &r, tree name, basic_block bb,
96 bool search_dom)
98 // Non-call exceptions mean we could throw in the middle of the
99 // block, so just punt on those for now.
100 if (cfun->can_throw_non_call_exceptions)
101 return false;
103 // We only care about the null / non-null property of pointers.
104 if (!POINTER_TYPE_P (TREE_TYPE (name)))
105 return false;
106 if (r.undefined_p () || r.lower_bound () != 0 || r.upper_bound () == 0)
107 return false;
108 // Check if pointers have any non-null dereferences.
109 if (non_null_deref_p (name, bb, search_dom))
111 // Remove zero from the range.
112 unsigned prec = TYPE_PRECISION (TREE_TYPE (name));
113 r.intersect (wi::one (prec), wi::max_value (prec, UNSIGNED));
114 return true;
116 return false;
119 // Allocate an populate the bitmap for NAME. An ON bit for a block
120 // index indicates there is a non-null reference in that block. In
121 // order to populate the bitmap, a quick run of all the immediate uses
122 // are made and the statement checked to see if a non-null dereference
123 // is made on that statement.
125 void
126 non_null_ref::process_name (tree name)
128 unsigned v = SSA_NAME_VERSION (name);
129 use_operand_p use_p;
130 imm_use_iterator iter;
131 bitmap b;
133 // Only tracked for pointers.
134 if (!POINTER_TYPE_P (TREE_TYPE (name)))
135 return;
137 // Already processed if a bitmap has been allocated.
138 if (m_nn[v])
139 return;
141 b = BITMAP_ALLOC (&m_bitmaps);
143 // Loop over each immediate use and see if it implies a non-null value.
144 FOR_EACH_IMM_USE_FAST (use_p, iter, name)
146 gimple *s = USE_STMT (use_p);
147 unsigned index = gimple_bb (s)->index;
149 // If bit is already set for this block, dont bother looking again.
150 if (bitmap_bit_p (b, index))
151 continue;
153 // If we can infer a nonnull range, then set the bit for this BB
154 if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)
155 && infer_nonnull_range (s, name))
156 bitmap_set_bit (b, index);
159 m_nn[v] = b;
162 // -------------------------------------------------------------------------
164 // This class represents the API into a cache of ranges for an SSA_NAME.
165 // Routines must be implemented to set, get, and query if a value is set.
167 class ssa_block_ranges
169 public:
170 virtual bool set_bb_range (const_basic_block bb, const irange &r) = 0;
171 virtual bool get_bb_range (irange &r, const_basic_block bb) = 0;
172 virtual bool bb_range_p (const_basic_block bb) = 0;
174 void dump(FILE *f);
177 // Print the list of known ranges for file F in a nice format.
179 void
180 ssa_block_ranges::dump (FILE *f)
182 basic_block bb;
183 int_range_max r;
185 FOR_EACH_BB_FN (bb, cfun)
186 if (get_bb_range (r, bb))
188 fprintf (f, "BB%d -> ", bb->index);
189 r.dump (f);
190 fprintf (f, "\n");
194 // This class implements the range cache as a linear vector, indexed by BB.
195 // It caches a varying and undefined range which are used instead of
196 // allocating new ones each time.
198 class sbr_vector : public ssa_block_ranges
200 public:
201 sbr_vector (tree t, irange_allocator *allocator);
203 virtual bool set_bb_range (const_basic_block bb, const irange &r) OVERRIDE;
204 virtual bool get_bb_range (irange &r, const_basic_block bb) OVERRIDE;
205 virtual bool bb_range_p (const_basic_block bb) OVERRIDE;
206 protected:
207 irange **m_tab; // Non growing vector.
208 int m_tab_size;
209 int_range<2> m_varying;
210 int_range<2> m_undefined;
211 tree m_type;
212 irange_allocator *m_irange_allocator;
213 void grow ();
217 // Initialize a block cache for an ssa_name of type T.
219 sbr_vector::sbr_vector (tree t, irange_allocator *allocator)
221 gcc_checking_assert (TYPE_P (t));
222 m_type = t;
223 m_irange_allocator = allocator;
224 m_tab_size = last_basic_block_for_fn (cfun) + 1;
225 m_tab = (irange **)allocator->get_memory (m_tab_size * sizeof (irange *));
226 memset (m_tab, 0, m_tab_size * sizeof (irange *));
228 // Create the cached type range.
229 m_varying.set_varying (t);
230 m_undefined.set_undefined ();
233 // Grow the vector when the CFG has increased in size.
235 void
236 sbr_vector::grow ()
238 int curr_bb_size = last_basic_block_for_fn (cfun);
239 gcc_checking_assert (curr_bb_size > m_tab_size);
241 // Increase the max of a)128, b)needed increase * 2, c)10% of current_size.
242 int inc = MAX ((curr_bb_size - m_tab_size) * 2, 128);
243 inc = MAX (inc, curr_bb_size / 10);
244 int new_size = inc + curr_bb_size;
246 // Allocate new memory, copy the old vector and clear the new space.
247 irange **t = (irange **)m_irange_allocator->get_memory (new_size
248 * sizeof (irange *));
249 memcpy (t, m_tab, m_tab_size * sizeof (irange *));
250 memset (t + m_tab_size, 0, (new_size - m_tab_size) * sizeof (irange *));
252 m_tab = t;
253 m_tab_size = new_size;
256 // Set the range for block BB to be R.
258 bool
259 sbr_vector::set_bb_range (const_basic_block bb, const irange &r)
261 irange *m;
262 if (bb->index >= m_tab_size)
263 grow ();
264 if (r.varying_p ())
265 m = &m_varying;
266 else if (r.undefined_p ())
267 m = &m_undefined;
268 else
269 m = m_irange_allocator->allocate (r);
270 m_tab[bb->index] = m;
271 return true;
274 // Return the range associated with block BB in R. Return false if
275 // there is no range.
277 bool
278 sbr_vector::get_bb_range (irange &r, const_basic_block bb)
280 if (bb->index >= m_tab_size)
281 return false;
282 irange *m = m_tab[bb->index];
283 if (m)
285 r = *m;
286 return true;
288 return false;
291 // Return true if a range is present.
293 bool
294 sbr_vector::bb_range_p (const_basic_block bb)
296 if (bb->index < m_tab_size)
297 return m_tab[bb->index] != NULL;
298 return false;
301 // This class implements the on entry cache via a sparse bitmap.
302 // It uses the quad bit routines to access 4 bits at a time.
303 // A value of 0 (the default) means there is no entry, and a value of
304 // 1 thru SBR_NUM represents an element in the m_range vector.
305 // Varying is given the first value (1) and pre-cached.
306 // SBR_NUM + 1 represents the value of UNDEFINED, and is never stored.
307 // SBR_NUM is the number of values that can be cached.
308 // Indexes are 1..SBR_NUM and are stored locally at m_range[0..SBR_NUM-1]
310 #define SBR_NUM 14
311 #define SBR_UNDEF SBR_NUM + 1
312 #define SBR_VARYING 1
314 class sbr_sparse_bitmap : public ssa_block_ranges
316 public:
317 sbr_sparse_bitmap (tree t, irange_allocator *allocator, bitmap_obstack *bm);
318 virtual bool set_bb_range (const_basic_block bb, const irange &r) OVERRIDE;
319 virtual bool get_bb_range (irange &r, const_basic_block bb) OVERRIDE;
320 virtual bool bb_range_p (const_basic_block bb) OVERRIDE;
321 private:
322 void bitmap_set_quad (bitmap head, int quad, int quad_value);
323 int bitmap_get_quad (const_bitmap head, int quad);
324 irange_allocator *m_irange_allocator;
325 irange *m_range[SBR_NUM];
326 bitmap bitvec;
327 tree m_type;
330 // Initialize a block cache for an ssa_name of type T.
332 sbr_sparse_bitmap::sbr_sparse_bitmap (tree t, irange_allocator *allocator,
333 bitmap_obstack *bm)
335 gcc_checking_assert (TYPE_P (t));
336 m_type = t;
337 bitvec = BITMAP_ALLOC (bm);
338 m_irange_allocator = allocator;
339 // Pre-cache varying.
340 m_range[0] = m_irange_allocator->allocate (2);
341 m_range[0]->set_varying (t);
342 // Pre-cache zero and non-zero values for pointers.
343 if (POINTER_TYPE_P (t))
345 m_range[1] = m_irange_allocator->allocate (2);
346 m_range[1]->set_nonzero (t);
347 m_range[2] = m_irange_allocator->allocate (2);
348 m_range[2]->set_zero (t);
350 else
351 m_range[1] = m_range[2] = NULL;
352 // Clear SBR_NUM entries.
353 for (int x = 3; x < SBR_NUM; x++)
354 m_range[x] = 0;
357 // Set 4 bit values in a sparse bitmap. This allows a bitmap to
358 // function as a sparse array of 4 bit values.
359 // QUAD is the index, QUAD_VALUE is the 4 bit value to set.
361 inline void
362 sbr_sparse_bitmap::bitmap_set_quad (bitmap head, int quad, int quad_value)
364 bitmap_set_aligned_chunk (head, quad, 4, (BITMAP_WORD) quad_value);
367 // Get a 4 bit value from a sparse bitmap. This allows a bitmap to
368 // function as a sparse array of 4 bit values.
369 // QUAD is the index.
370 inline int
371 sbr_sparse_bitmap::bitmap_get_quad (const_bitmap head, int quad)
373 return (int) bitmap_get_aligned_chunk (head, quad, 4);
376 // Set the range on entry to basic block BB to R.
378 bool
379 sbr_sparse_bitmap::set_bb_range (const_basic_block bb, const irange &r)
381 if (r.undefined_p ())
383 bitmap_set_quad (bitvec, bb->index, SBR_UNDEF);
384 return true;
387 // Loop thru the values to see if R is already present.
388 for (int x = 0; x < SBR_NUM; x++)
389 if (!m_range[x] || r == *(m_range[x]))
391 if (!m_range[x])
392 m_range[x] = m_irange_allocator->allocate (r);
393 bitmap_set_quad (bitvec, bb->index, x + 1);
394 return true;
396 // All values are taken, default to VARYING.
397 bitmap_set_quad (bitvec, bb->index, SBR_VARYING);
398 return false;
401 // Return the range associated with block BB in R. Return false if
402 // there is no range.
404 bool
405 sbr_sparse_bitmap::get_bb_range (irange &r, const_basic_block bb)
407 int value = bitmap_get_quad (bitvec, bb->index);
409 if (!value)
410 return false;
412 gcc_checking_assert (value <= SBR_UNDEF);
413 if (value == SBR_UNDEF)
414 r.set_undefined ();
415 else
416 r = *(m_range[value - 1]);
417 return true;
420 // Return true if a range is present.
422 bool
423 sbr_sparse_bitmap::bb_range_p (const_basic_block bb)
425 return (bitmap_get_quad (bitvec, bb->index) != 0);
428 // -------------------------------------------------------------------------
430 // Initialize the block cache.
432 block_range_cache::block_range_cache ()
434 bitmap_obstack_initialize (&m_bitmaps);
435 m_ssa_ranges.create (0);
436 m_ssa_ranges.safe_grow_cleared (num_ssa_names);
437 m_irange_allocator = new irange_allocator;
440 // Remove any m_block_caches which have been created.
442 block_range_cache::~block_range_cache ()
444 delete m_irange_allocator;
445 // Release the vector itself.
446 m_ssa_ranges.release ();
447 bitmap_obstack_release (&m_bitmaps);
450 // Set the range for NAME on entry to block BB to R.
451 // If it has not been accessed yet, allocate it first.
453 bool
454 block_range_cache::set_bb_range (tree name, const_basic_block bb,
455 const irange &r)
457 unsigned v = SSA_NAME_VERSION (name);
458 if (v >= m_ssa_ranges.length ())
459 m_ssa_ranges.safe_grow_cleared (num_ssa_names + 1);
461 if (!m_ssa_ranges[v])
463 // Use sparse representation if there are too many basic blocks.
464 if (last_basic_block_for_fn (cfun) > param_evrp_sparse_threshold)
466 void *r = m_irange_allocator->get_memory (sizeof (sbr_sparse_bitmap));
467 m_ssa_ranges[v] = new (r) sbr_sparse_bitmap (TREE_TYPE (name),
468 m_irange_allocator,
469 &m_bitmaps);
471 else
473 // Otherwise use the default vector implemntation.
474 void *r = m_irange_allocator->get_memory (sizeof (sbr_vector));
475 m_ssa_ranges[v] = new (r) sbr_vector (TREE_TYPE (name),
476 m_irange_allocator);
479 return m_ssa_ranges[v]->set_bb_range (bb, r);
483 // Return a pointer to the ssa_block_cache for NAME. If it has not been
484 // accessed yet, return NULL.
486 inline ssa_block_ranges *
487 block_range_cache::query_block_ranges (tree name)
489 unsigned v = SSA_NAME_VERSION (name);
490 if (v >= m_ssa_ranges.length () || !m_ssa_ranges[v])
491 return NULL;
492 return m_ssa_ranges[v];
497 // Return the range for NAME on entry to BB in R. Return true if there
498 // is one.
500 bool
501 block_range_cache::get_bb_range (irange &r, tree name, const_basic_block bb)
503 ssa_block_ranges *ptr = query_block_ranges (name);
504 if (ptr)
505 return ptr->get_bb_range (r, bb);
506 return false;
509 // Return true if NAME has a range set in block BB.
511 bool
512 block_range_cache::bb_range_p (tree name, const_basic_block bb)
514 ssa_block_ranges *ptr = query_block_ranges (name);
515 if (ptr)
516 return ptr->bb_range_p (bb);
517 return false;
520 // Print all known block caches to file F.
522 void
523 block_range_cache::dump (FILE *f)
525 unsigned x;
526 for (x = 0; x < m_ssa_ranges.length (); ++x)
528 if (m_ssa_ranges[x])
530 fprintf (f, " Ranges for ");
531 print_generic_expr (f, ssa_name (x), TDF_NONE);
532 fprintf (f, ":\n");
533 m_ssa_ranges[x]->dump (f);
534 fprintf (f, "\n");
539 // Print all known ranges on entry to blobk BB to file F.
541 void
542 block_range_cache::dump (FILE *f, basic_block bb, bool print_varying)
544 unsigned x;
545 int_range_max r;
546 bool summarize_varying = false;
547 for (x = 1; x < m_ssa_ranges.length (); ++x)
549 if (!gimple_range_ssa_p (ssa_name (x)))
550 continue;
551 if (m_ssa_ranges[x] && m_ssa_ranges[x]->get_bb_range (r, bb))
553 if (!print_varying && r.varying_p ())
555 summarize_varying = true;
556 continue;
558 print_generic_expr (f, ssa_name (x), TDF_NONE);
559 fprintf (f, "\t");
560 r.dump(f);
561 fprintf (f, "\n");
564 // If there were any varying entries, lump them all together.
565 if (summarize_varying)
567 fprintf (f, "VARYING_P on entry : ");
568 for (x = 1; x < num_ssa_names; ++x)
570 if (!gimple_range_ssa_p (ssa_name (x)))
571 continue;
572 if (m_ssa_ranges[x] && m_ssa_ranges[x]->get_bb_range (r, bb))
574 if (r.varying_p ())
576 print_generic_expr (f, ssa_name (x), TDF_NONE);
577 fprintf (f, " ");
581 fprintf (f, "\n");
585 // -------------------------------------------------------------------------
587 // Initialize a global cache.
589 ssa_global_cache::ssa_global_cache ()
591 m_tab.create (0);
592 m_irange_allocator = new irange_allocator;
595 // Deconstruct a global cache.
597 ssa_global_cache::~ssa_global_cache ()
599 m_tab.release ();
600 delete m_irange_allocator;
603 // Retrieve the global range of NAME from cache memory if it exists.
604 // Return the value in R.
606 bool
607 ssa_global_cache::get_global_range (irange &r, tree name) const
609 unsigned v = SSA_NAME_VERSION (name);
610 if (v >= m_tab.length ())
611 return false;
613 irange *stow = m_tab[v];
614 if (!stow)
615 return false;
616 r = *stow;
617 return true;
620 // Set the range for NAME to R in the global cache.
621 // Return TRUE if there was already a range set, otherwise false.
623 bool
624 ssa_global_cache::set_global_range (tree name, const irange &r)
626 unsigned v = SSA_NAME_VERSION (name);
627 if (v >= m_tab.length ())
628 m_tab.safe_grow_cleared (num_ssa_names + 1);
630 irange *m = m_tab[v];
631 if (m && m->fits_p (r))
632 *m = r;
633 else
634 m_tab[v] = m_irange_allocator->allocate (r);
635 return m != NULL;
638 // Set the range for NAME to R in the glonbal cache.
640 void
641 ssa_global_cache::clear_global_range (tree name)
643 unsigned v = SSA_NAME_VERSION (name);
644 if (v >= m_tab.length ())
645 m_tab.safe_grow_cleared (num_ssa_names + 1);
646 m_tab[v] = NULL;
649 // Clear the global cache.
651 void
652 ssa_global_cache::clear ()
654 if (m_tab.address ())
655 memset (m_tab.address(), 0, m_tab.length () * sizeof (irange *));
658 // Dump the contents of the global cache to F.
660 void
661 ssa_global_cache::dump (FILE *f)
663 /* Cleared after the table header has been printed. */
664 bool print_header = true;
665 for (unsigned x = 1; x < num_ssa_names; x++)
667 int_range_max r;
668 if (gimple_range_ssa_p (ssa_name (x)) &&
669 get_global_range (r, ssa_name (x)) && !r.varying_p ())
671 if (print_header)
673 /* Print the header only when there's something else
674 to print below. */
675 fprintf (f, "Non-varying global ranges:\n");
676 fprintf (f, "=========================:\n");
677 print_header = false;
680 print_generic_expr (f, ssa_name (x), TDF_NONE);
681 fprintf (f, " : ");
682 r.dump (f);
683 fprintf (f, "\n");
687 if (!print_header)
688 fputc ('\n', f);
691 // --------------------------------------------------------------------------
694 // This class will manage the timestamps for each ssa_name.
695 // When a value is calculated, the timestamp is set to the current time.
696 // Current time is then incremented. Any dependencies will already have
697 // been calculated, and will thus have older timestamps.
698 // If one of those values is ever calculated again, it will get a newer
699 // timestamp, and the "current_p" check will fail.
701 class temporal_cache
703 public:
704 temporal_cache ();
705 ~temporal_cache ();
706 bool current_p (tree name, tree dep1, tree dep2) const;
707 void set_timestamp (tree name);
708 void set_always_current (tree name);
709 private:
710 unsigned temporal_value (unsigned ssa) const;
712 unsigned m_current_time;
713 vec <unsigned> m_timestamp;
716 inline
717 temporal_cache::temporal_cache ()
719 m_current_time = 1;
720 m_timestamp.create (0);
721 m_timestamp.safe_grow_cleared (num_ssa_names);
724 inline
725 temporal_cache::~temporal_cache ()
727 m_timestamp.release ();
730 // Return the timestamp value for SSA, or 0 if there isnt one.
732 inline unsigned
733 temporal_cache::temporal_value (unsigned ssa) const
735 if (ssa >= m_timestamp.length ())
736 return 0;
737 return m_timestamp[ssa];
740 // Return TRUE if the timestampe for NAME is newer than any of its dependents.
741 // Up to 2 dependencies can be checked.
743 bool
744 temporal_cache::current_p (tree name, tree dep1, tree dep2) const
746 unsigned ts = temporal_value (SSA_NAME_VERSION (name));
747 if (ts == 0)
748 return true;
750 // Any non-registered dependencies will have a value of 0 and thus be older.
751 // Return true if time is newer than either dependent.
753 if (dep1 && ts < temporal_value (SSA_NAME_VERSION (dep1)))
754 return false;
755 if (dep2 && ts < temporal_value (SSA_NAME_VERSION (dep2)))
756 return false;
758 return true;
761 // This increments the global timer and sets the timestamp for NAME.
763 inline void
764 temporal_cache::set_timestamp (tree name)
766 unsigned v = SSA_NAME_VERSION (name);
767 if (v >= m_timestamp.length ())
768 m_timestamp.safe_grow_cleared (num_ssa_names + 20);
769 m_timestamp[v] = ++m_current_time;
772 // Set the timestamp to 0, marking it as "always up to date".
774 inline void
775 temporal_cache::set_always_current (tree name)
777 unsigned v = SSA_NAME_VERSION (name);
778 if (v >= m_timestamp.length ())
779 m_timestamp.safe_grow_cleared (num_ssa_names + 20);
780 m_timestamp[v] = 0;
783 // --------------------------------------------------------------------------
785 // This class provides an abstraction of a list of blocks to be updated
786 // by the cache. It is currently a stack but could be changed. It also
787 // maintains a list of blocks which have failed propagation, and does not
788 // enter any of those blocks into the list.
790 // A vector over the BBs is maintained, and an entry of 0 means it is not in
791 // a list. Otherwise, the entry is the next block in the list. -1 terminates
792 // the list. m_head points to the top of the list, -1 if the list is empty.
794 class update_list
796 public:
797 update_list ();
798 ~update_list ();
799 void add (basic_block bb);
800 basic_block pop ();
801 inline bool empty_p () { return m_update_head == -1; }
802 inline void clear_failures () { bitmap_clear (m_propfail); }
803 inline void propagation_failed (basic_block bb)
804 { bitmap_set_bit (m_propfail, bb->index); }
805 private:
806 vec<int> m_update_list;
807 int m_update_head;
808 bitmap m_propfail;
811 // Create an update list.
813 update_list::update_list ()
815 m_update_list.create (0);
816 m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun) + 64);
817 m_update_head = -1;
818 m_propfail = BITMAP_ALLOC (NULL);
821 // Destroy an update list.
823 update_list::~update_list ()
825 m_update_list.release ();
826 BITMAP_FREE (m_propfail);
829 // Add BB to the list of blocks to update, unless it's already in the list.
831 void
832 update_list::add (basic_block bb)
834 int i = bb->index;
835 // If propagation has failed for BB, or its already in the list, don't
836 // add it again.
837 if ((unsigned)i >= m_update_list.length ())
838 m_update_list.safe_grow_cleared (i + 64);
839 if (!m_update_list[i] && !bitmap_bit_p (m_propfail, i))
841 if (empty_p ())
843 m_update_head = i;
844 m_update_list[i] = -1;
846 else
848 gcc_checking_assert (m_update_head > 0);
849 m_update_list[i] = m_update_head;
850 m_update_head = i;
855 // Remove a block from the list.
857 basic_block
858 update_list::pop ()
860 gcc_checking_assert (!empty_p ());
861 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, m_update_head);
862 int pop = m_update_head;
863 m_update_head = m_update_list[pop];
864 m_update_list[pop] = 0;
865 return bb;
868 // --------------------------------------------------------------------------
870 ranger_cache::ranger_cache (int not_executable_flag)
871 : m_gori (not_executable_flag)
873 m_workback.create (0);
874 m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun));
875 m_temporal = new temporal_cache;
876 // If DOM info is available, spawn an oracle as well.
877 if (dom_info_available_p (CDI_DOMINATORS))
878 m_oracle = new dom_oracle ();
879 else
880 m_oracle = NULL;
882 unsigned x, lim = last_basic_block_for_fn (cfun);
883 // Calculate outgoing range info upfront. This will fully populate the
884 // m_maybe_variant bitmap which will help eliminate processing of names
885 // which never have their ranges adjusted.
886 for (x = 0; x < lim ; x++)
888 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, x);
889 if (bb)
890 m_gori.exports (bb);
892 m_update = new update_list ();
895 ranger_cache::~ranger_cache ()
897 delete m_update;
898 if (m_oracle)
899 delete m_oracle;
900 delete m_temporal;
901 m_workback.release ();
904 // Dump the global caches to file F. if GORI_DUMP is true, dump the
905 // gori map as well.
907 void
908 ranger_cache::dump (FILE *f)
910 m_globals.dump (f);
911 fprintf (f, "\n");
914 // Dump the caches for basic block BB to file F.
916 void
917 ranger_cache::dump_bb (FILE *f, basic_block bb)
919 m_gori.gori_map::dump (f, bb, false);
920 m_on_entry.dump (f, bb);
921 if (m_oracle)
922 m_oracle->dump (f, bb);
925 // Get the global range for NAME, and return in R. Return false if the
926 // global range is not set, and return the legacy global value in R.
928 bool
929 ranger_cache::get_global_range (irange &r, tree name) const
931 if (m_globals.get_global_range (r, name))
932 return true;
933 r = gimple_range_global (name);
934 return false;
937 // Get the global range for NAME, and return in R. Return false if the
938 // global range is not set, and R will contain the legacy global value.
939 // CURRENT_P is set to true if the value was in cache and not stale.
940 // Otherwise, set CURRENT_P to false and mark as it always current.
941 // If the global cache did not have a value, initialize it as well.
942 // After this call, the global cache will have a value.
944 bool
945 ranger_cache::get_global_range (irange &r, tree name, bool &current_p)
947 bool had_global = get_global_range (r, name);
949 // If there was a global value, set current flag, otherwise set a value.
950 current_p = false;
951 if (had_global)
952 current_p = r.singleton_p ()
953 || m_temporal->current_p (name, m_gori.depend1 (name),
954 m_gori.depend2 (name));
955 else
956 m_globals.set_global_range (name, r);
958 // If the existing value was not current, mark it as always current.
959 if (!current_p)
960 m_temporal->set_always_current (name);
961 return current_p;
964 // Set the global range of NAME to R and give it a timestamp.
966 void
967 ranger_cache::set_global_range (tree name, const irange &r)
969 if (m_globals.set_global_range (name, r))
971 // If there was already a range set, propagate the new value.
972 basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (name));
973 if (!bb)
974 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
976 if (DEBUG_RANGE_CACHE)
977 fprintf (dump_file, " GLOBAL :");
979 propagate_updated_value (name, bb);
981 // Constants no longer need to tracked. Any further refinement has to be
982 // undefined. Propagation works better with constants. PR 100512.
983 // Pointers which resolve to non-zero also do not need
984 // tracking in the cache as they will never change. See PR 98866.
985 // Timestamp must always be updated, or dependent calculations may
986 // not include this latest value. PR 100774.
988 if (r.singleton_p ()
989 || (POINTER_TYPE_P (TREE_TYPE (name)) && r.nonzero_p ()))
990 m_gori.set_range_invariant (name);
991 m_temporal->set_timestamp (name);
994 // Provide lookup for the gori-computes class to access the best known range
995 // of an ssa_name in any given basic block. Note, this does no additonal
996 // lookups, just accesses the data that is already known.
998 // Get the range of NAME when the def occurs in block BB. If BB is NULL
999 // get the best global value available.
1001 void
1002 ranger_cache::range_of_def (irange &r, tree name, basic_block bb)
1004 gcc_checking_assert (gimple_range_ssa_p (name));
1005 gcc_checking_assert (!bb || bb == gimple_bb (SSA_NAME_DEF_STMT (name)));
1007 // Pick up the best global range available.
1008 if (!m_globals.get_global_range (r, name))
1010 // If that fails, try to calculate the range using just global values.
1011 gimple *s = SSA_NAME_DEF_STMT (name);
1012 if (gimple_get_lhs (s) == name)
1013 fold_range (r, s, get_global_range_query ());
1014 else
1015 r = gimple_range_global (name);
1018 if (bb)
1019 m_non_null.adjust_range (r, name, bb, false);
1022 // Get the range of NAME as it occurs on entry to block BB.
1024 void
1025 ranger_cache::entry_range (irange &r, tree name, basic_block bb)
1027 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1029 r = gimple_range_global (name);
1030 return;
1033 // Look for the on-entry value of name in BB from the cache.
1034 // Otherwise pick up the best available global value.
1035 if (!m_on_entry.get_bb_range (r, name, bb))
1036 range_of_def (r, name);
1038 m_non_null.adjust_range (r, name, bb, false);
1041 // Get the range of NAME as it occurs on exit from block BB.
1043 void
1044 ranger_cache::exit_range (irange &r, tree name, basic_block bb)
1046 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1048 r = gimple_range_global (name);
1049 return;
1052 gimple *s = SSA_NAME_DEF_STMT (name);
1053 basic_block def_bb = gimple_bb (s);
1054 if (def_bb == bb)
1055 range_of_def (r, name, bb);
1056 else
1057 entry_range (r, name, bb);
1061 // Implement range_of_expr.
1063 bool
1064 ranger_cache::range_of_expr (irange &r, tree name, gimple *stmt)
1066 if (!gimple_range_ssa_p (name))
1068 get_tree_range (r, name, stmt);
1069 return true;
1072 basic_block bb = gimple_bb (stmt);
1073 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1074 basic_block def_bb = gimple_bb (def_stmt);
1076 if (bb == def_bb)
1077 range_of_def (r, name, bb);
1078 else
1079 entry_range (r, name, bb);
1080 return true;
1084 // Implement range_on_edge. Always return the best available range.
1086 bool
1087 ranger_cache::range_on_edge (irange &r, edge e, tree expr)
1089 if (gimple_range_ssa_p (expr))
1091 exit_range (r, expr, e->src);
1092 int_range_max edge_range;
1093 if (m_gori.outgoing_edge_range_p (edge_range, e, expr, *this))
1094 r.intersect (edge_range);
1095 return true;
1098 return get_tree_range (r, expr, NULL);
1102 // Return a static range for NAME on entry to basic block BB in R. If
1103 // calc is true, fill any cache entries required between BB and the
1104 // def block for NAME. Otherwise, return false if the cache is empty.
1106 bool
1107 ranger_cache::block_range (irange &r, basic_block bb, tree name, bool calc)
1109 gcc_checking_assert (gimple_range_ssa_p (name));
1111 // If there are no range calculations anywhere in the IL, global range
1112 // applies everywhere, so don't bother caching it.
1113 if (!m_gori.has_edge_range_p (name))
1114 return false;
1116 if (calc)
1118 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1119 basic_block def_bb = NULL;
1120 if (def_stmt)
1121 def_bb = gimple_bb (def_stmt);;
1122 if (!def_bb)
1124 // If we get to the entry block, this better be a default def
1125 // or range_on_entry was called for a block not dominated by
1126 // the def.
1127 gcc_checking_assert (SSA_NAME_IS_DEFAULT_DEF (name));
1128 def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1131 // There is no range on entry for the definition block.
1132 if (def_bb == bb)
1133 return false;
1135 // Otherwise, go figure out what is known in predecessor blocks.
1136 fill_block_cache (name, bb, def_bb);
1137 gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
1139 return m_on_entry.get_bb_range (r, name, bb);
1142 // If there is anything in the propagation update_list, continue
1143 // processing NAME until the list of blocks is empty.
1145 void
1146 ranger_cache::propagate_cache (tree name)
1148 basic_block bb;
1149 edge_iterator ei;
1150 edge e;
1151 int_range_max new_range;
1152 int_range_max current_range;
1153 int_range_max e_range;
1155 // Process each block by seeing if its calculated range on entry is
1156 // the same as its cached value. If there is a difference, update
1157 // the cache to reflect the new value, and check to see if any
1158 // successors have cache entries which may need to be checked for
1159 // updates.
1161 while (!m_update->empty_p ())
1163 bb = m_update->pop ();
1164 gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
1165 m_on_entry.get_bb_range (current_range, name, bb);
1167 if (DEBUG_RANGE_CACHE)
1169 fprintf (dump_file, "FWD visiting block %d for ", bb->index);
1170 print_generic_expr (dump_file, name, TDF_SLIM);
1171 fprintf (dump_file, " starting range : ");
1172 current_range.dump (dump_file);
1173 fprintf (dump_file, "\n");
1176 // Calculate the "new" range on entry by unioning the pred edges.
1177 new_range.set_undefined ();
1178 FOR_EACH_EDGE (e, ei, bb->preds)
1180 range_on_edge (e_range, e, name);
1181 if (DEBUG_RANGE_CACHE)
1183 fprintf (dump_file, " edge %d->%d :", e->src->index, bb->index);
1184 e_range.dump (dump_file);
1185 fprintf (dump_file, "\n");
1187 new_range.union_ (e_range);
1188 if (new_range.varying_p ())
1189 break;
1192 // If the range on entry has changed, update it.
1193 if (new_range != current_range)
1195 bool ok_p = m_on_entry.set_bb_range (name, bb, new_range);
1196 // If the cache couldn't set the value, mark it as failed.
1197 if (!ok_p)
1198 m_update->propagation_failed (bb);
1199 if (DEBUG_RANGE_CACHE)
1201 if (!ok_p)
1203 fprintf (dump_file, " Cache failure to store value:");
1204 print_generic_expr (dump_file, name, TDF_SLIM);
1205 fprintf (dump_file, " ");
1207 else
1209 fprintf (dump_file, " Updating range to ");
1210 new_range.dump (dump_file);
1212 fprintf (dump_file, "\n Updating blocks :");
1214 // Mark each successor that has a range to re-check its range
1215 FOR_EACH_EDGE (e, ei, bb->succs)
1216 if (m_on_entry.bb_range_p (name, e->dest))
1218 if (DEBUG_RANGE_CACHE)
1219 fprintf (dump_file, " bb%d",e->dest->index);
1220 m_update->add (e->dest);
1222 if (DEBUG_RANGE_CACHE)
1223 fprintf (dump_file, "\n");
1226 if (DEBUG_RANGE_CACHE)
1228 fprintf (dump_file, "DONE visiting blocks for ");
1229 print_generic_expr (dump_file, name, TDF_SLIM);
1230 fprintf (dump_file, "\n");
1232 m_update->clear_failures ();
1235 // Check to see if an update to the value for NAME in BB has any effect
1236 // on values already in the on-entry cache for successor blocks.
1237 // If it does, update them. Don't visit any blocks which dont have a cache
1238 // entry.
1240 void
1241 ranger_cache::propagate_updated_value (tree name, basic_block bb)
1243 edge e;
1244 edge_iterator ei;
1246 // The update work list should be empty at this point.
1247 gcc_checking_assert (m_update->empty_p ());
1248 gcc_checking_assert (bb);
1250 if (DEBUG_RANGE_CACHE)
1252 fprintf (dump_file, " UPDATE cache for ");
1253 print_generic_expr (dump_file, name, TDF_SLIM);
1254 fprintf (dump_file, " in BB %d : successors : ", bb->index);
1256 FOR_EACH_EDGE (e, ei, bb->succs)
1258 // Only update active cache entries.
1259 if (m_on_entry.bb_range_p (name, e->dest))
1261 m_update->add (e->dest);
1262 if (DEBUG_RANGE_CACHE)
1263 fprintf (dump_file, " UPDATE: bb%d", e->dest->index);
1266 if (!m_update->empty_p ())
1268 if (DEBUG_RANGE_CACHE)
1269 fprintf (dump_file, "\n");
1270 propagate_cache (name);
1272 else
1274 if (DEBUG_RANGE_CACHE)
1275 fprintf (dump_file, " : No updates!\n");
1279 // Make sure that the range-on-entry cache for NAME is set for block BB.
1280 // Work back through the CFG to DEF_BB ensuring the range is calculated
1281 // on the block/edges leading back to that point.
1283 void
1284 ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
1286 edge_iterator ei;
1287 edge e;
1288 int_range_max block_result;
1289 int_range_max undefined;
1291 // At this point we shouldn't be looking at the def, entry or exit block.
1292 gcc_checking_assert (bb != def_bb && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
1293 bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
1295 // If the block cache is set, then we've already visited this block.
1296 if (m_on_entry.bb_range_p (name, bb))
1297 return;
1299 // Visit each block back to the DEF. Initialize each one to UNDEFINED.
1300 // m_visited at the end will contain all the blocks that we needed to set
1301 // the range_on_entry cache for.
1302 m_workback.truncate (0);
1303 m_workback.quick_push (bb);
1304 undefined.set_undefined ();
1305 m_on_entry.set_bb_range (name, bb, undefined);
1306 gcc_checking_assert (m_update->empty_p ());
1308 if (DEBUG_RANGE_CACHE)
1310 fprintf (dump_file, "\n");
1311 print_generic_expr (dump_file, name, TDF_SLIM);
1312 fprintf (dump_file, " : ");
1315 // If there are dominators, check if a dominators can supply the range.
1316 if (dom_info_available_p (CDI_DOMINATORS)
1317 && range_from_dom (block_result, name, bb))
1319 m_on_entry.set_bb_range (name, bb, block_result);
1320 if (DEBUG_RANGE_CACHE)
1322 fprintf (dump_file, "Filled from dominator! : ");
1323 block_result.dump (dump_file);
1324 fprintf (dump_file, "\n");
1326 return;
1329 while (m_workback.length () > 0)
1331 basic_block node = m_workback.pop ();
1332 if (DEBUG_RANGE_CACHE)
1334 fprintf (dump_file, "BACK visiting block %d for ", node->index);
1335 print_generic_expr (dump_file, name, TDF_SLIM);
1336 fprintf (dump_file, "\n");
1339 FOR_EACH_EDGE (e, ei, node->preds)
1341 basic_block pred = e->src;
1342 int_range_max r;
1344 if (DEBUG_RANGE_CACHE)
1345 fprintf (dump_file, " %d->%d ",e->src->index, e->dest->index);
1347 // If the pred block is the def block add this BB to update list.
1348 if (pred == def_bb)
1350 m_update->add (node);
1351 continue;
1354 // If the pred is entry but NOT def, then it is used before
1355 // defined, it'll get set to [] and no need to update it.
1356 if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1358 if (DEBUG_RANGE_CACHE)
1359 fprintf (dump_file, "entry: bail.");
1360 continue;
1363 // Regardless of whether we have visited pred or not, if the
1364 // pred has a non-null reference, revisit this block.
1365 // Don't search the DOM tree.
1366 if (m_non_null.non_null_deref_p (name, pred, false))
1368 if (DEBUG_RANGE_CACHE)
1369 fprintf (dump_file, "nonnull: update ");
1370 m_update->add (node);
1373 // If the pred block already has a range, or if it can contribute
1374 // something new. Ie, the edge generates a range of some sort.
1375 if (m_on_entry.get_bb_range (r, name, pred))
1377 if (DEBUG_RANGE_CACHE)
1379 fprintf (dump_file, "has cache, ");
1380 r.dump (dump_file);
1381 fprintf (dump_file, ", ");
1383 if (!r.undefined_p () || m_gori.has_edge_range_p (name, e))
1385 m_update->add (node);
1386 if (DEBUG_RANGE_CACHE)
1387 fprintf (dump_file, "update. ");
1389 continue;
1392 if (DEBUG_RANGE_CACHE)
1393 fprintf (dump_file, "pushing undefined pred block.\n");
1394 // If the pred hasn't been visited (has no range), add it to
1395 // the list.
1396 gcc_checking_assert (!m_on_entry.bb_range_p (name, pred));
1397 m_on_entry.set_bb_range (name, pred, undefined);
1398 m_workback.quick_push (pred);
1402 if (DEBUG_RANGE_CACHE)
1403 fprintf (dump_file, "\n");
1405 // Now fill in the marked blocks with values.
1406 propagate_cache (name);
1407 if (DEBUG_RANGE_CACHE)
1408 fprintf (dump_file, " Propagation update done.\n");
1412 // Check to see if we can simply get the range from the dominator.
1414 bool
1415 ranger_cache::range_from_dom (irange &r, tree name, basic_block bb)
1417 gcc_checking_assert (dom_info_available_p (CDI_DOMINATORS));
1419 // Search back to the definition block or entry block.
1420 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1421 if (def_bb == NULL)
1422 def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1424 // Flag if we encounter a block with non-null set.
1425 bool non_null = false;
1426 for (bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1427 bb && bb != def_bb;
1428 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1430 // If there is an outgoing range, the on-entry value won't work.
1431 if (m_gori.has_edge_range_p (name, bb))
1433 // Check if we can seed this block with a dominator value. THis will
1434 // prevent the ache from being filled back further than this.
1435 if (bb != def_bb && range_from_dom (r, name, bb))
1436 m_on_entry.set_bb_range (name, bb, r);
1437 return false;
1440 // Flag if we see a non-null reference during this walk.
1441 if (m_non_null.non_null_deref_p (name, bb, false))
1442 non_null = true;
1444 // If range-on-entry is set in this block, it can be used.
1445 if (m_on_entry.get_bb_range (r, name, bb))
1447 // Apply non-null if appropriate.
1448 if (r.varying_p () && non_null)
1450 gcc_checking_assert (POINTER_TYPE_P (TREE_TYPE (name)));
1451 r.set_nonzero (TREE_TYPE (name));
1453 return true;
1456 // If this is the def block, and NAME is an export, then this value
1457 // cannot be used.
1458 if (bb == def_bb && m_gori.has_edge_range_p (name, bb))
1459 return false;
1461 // Otherwise choose the global value and use it.
1462 get_global_range (r, name);
1463 if (r.varying_p () && non_null)
1465 gcc_checking_assert (POINTER_TYPE_P (TREE_TYPE (name)));
1466 r.set_nonzero (TREE_TYPE (name));
1468 return true;