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)
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/>. */
23 #include "coretypes.h"
25 #include "insn-codes.h"
29 #include "gimple-pretty-print.h"
30 #include "gimple-range.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
);
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.
58 non_null_ref::non_null_deref_p (tree name
, basic_block bb
, bool search_dom
)
60 if (!POINTER_TYPE_P (TREE_TYPE (name
)))
63 unsigned v
= SSA_NAME_VERSION (name
);
64 if (v
>= m_nn
.length ())
65 m_nn
.safe_grow_cleared (num_ssa_names
+ 1);
70 if (bitmap_bit_p (m_nn
[v
], bb
->index
))
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
)
83 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
84 if (bitmap_bit_p (m_nn
[v
], bb
->index
))
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.
95 non_null_ref::adjust_range (irange
&r
, tree name
, basic_block bb
,
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
)
103 // We only care about the null / non-null property of pointers.
104 if (!POINTER_TYPE_P (TREE_TYPE (name
)))
106 if (r
.undefined_p () || r
.lower_bound () != 0 || r
.upper_bound () == 0)
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
));
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.
126 non_null_ref::process_name (tree name
)
128 unsigned v
= SSA_NAME_VERSION (name
);
130 imm_use_iterator iter
;
133 // Only tracked for pointers.
134 if (!POINTER_TYPE_P (TREE_TYPE (name
)))
137 // Already processed if a bitmap has been allocated.
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
))
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
);
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
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;
177 // Print the list of known ranges for file F in a nice format.
180 ssa_block_ranges::dump (FILE *f
)
185 FOR_EACH_BB_FN (bb
, cfun
)
186 if (get_bb_range (r
, bb
))
188 fprintf (f
, "BB%d -> ", bb
->index
);
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
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
;
207 irange
**m_tab
; // Non growing vector.
209 int_range
<2> m_varying
;
210 int_range
<2> m_undefined
;
212 irange_allocator
*m_irange_allocator
;
216 // Initialize a block cache for an ssa_name of type T.
218 sbr_vector::sbr_vector (tree t
, irange_allocator
*allocator
)
220 gcc_checking_assert (TYPE_P (t
));
222 m_irange_allocator
= allocator
;
223 m_tab_size
= last_basic_block_for_fn (cfun
) + 1;
224 m_tab
= (irange
**)allocator
->get_memory (m_tab_size
* sizeof (irange
*));
225 memset (m_tab
, 0, m_tab_size
* sizeof (irange
*));
227 // Create the cached type range.
228 m_varying
.set_varying (t
);
229 m_undefined
.set_undefined ();
232 // Set the range for block BB to be R.
235 sbr_vector::set_bb_range (const_basic_block bb
, const irange
&r
)
238 gcc_checking_assert (bb
->index
< m_tab_size
);
241 else if (r
.undefined_p ())
244 m
= m_irange_allocator
->allocate (r
);
245 m_tab
[bb
->index
] = m
;
249 // Return the range associated with block BB in R. Return false if
250 // there is no range.
253 sbr_vector::get_bb_range (irange
&r
, const_basic_block bb
)
255 gcc_checking_assert (bb
->index
< m_tab_size
);
256 irange
*m
= m_tab
[bb
->index
];
265 // Return true if a range is present.
268 sbr_vector::bb_range_p (const_basic_block bb
)
270 gcc_checking_assert (bb
->index
< m_tab_size
);
271 return m_tab
[bb
->index
] != NULL
;
274 // This class implements the on entry cache via a sparse bitmap.
275 // It uses the quad bit routines to access 4 bits at a time.
276 // A value of 0 (the default) means there is no entry, and a value of
277 // 1 thru SBR_NUM represents an element in the m_range vector.
278 // Varying is given the first value (1) and pre-cached.
279 // SBR_NUM + 1 represents the value of UNDEFINED, and is never stored.
280 // SBR_NUM is the number of values that can be cached.
281 // Indexes are 1..SBR_NUM and are stored locally at m_range[0..SBR_NUM-1]
284 #define SBR_UNDEF SBR_NUM + 1
285 #define SBR_VARYING 1
287 class sbr_sparse_bitmap
: public ssa_block_ranges
290 sbr_sparse_bitmap (tree t
, irange_allocator
*allocator
, bitmap_obstack
*bm
);
291 virtual bool set_bb_range (const_basic_block bb
, const irange
&r
) OVERRIDE
;
292 virtual bool get_bb_range (irange
&r
, const_basic_block bb
) OVERRIDE
;
293 virtual bool bb_range_p (const_basic_block bb
) OVERRIDE
;
295 void bitmap_set_quad (bitmap head
, int quad
, int quad_value
);
296 int bitmap_get_quad (const_bitmap head
, int quad
);
297 irange_allocator
*m_irange_allocator
;
298 irange
*m_range
[SBR_NUM
];
303 // Initialize a block cache for an ssa_name of type T.
305 sbr_sparse_bitmap::sbr_sparse_bitmap (tree t
, irange_allocator
*allocator
,
308 gcc_checking_assert (TYPE_P (t
));
310 bitvec
= BITMAP_ALLOC (bm
);
311 m_irange_allocator
= allocator
;
312 // Pre-cache varying.
313 m_range
[0] = m_irange_allocator
->allocate (2);
314 m_range
[0]->set_varying (t
);
315 // Pre-cache zero and non-zero values for pointers.
316 if (POINTER_TYPE_P (t
))
318 m_range
[1] = m_irange_allocator
->allocate (2);
319 m_range
[1]->set_nonzero (t
);
320 m_range
[2] = m_irange_allocator
->allocate (2);
321 m_range
[2]->set_zero (t
);
324 m_range
[1] = m_range
[2] = NULL
;
325 // Clear SBR_NUM entries.
326 for (int x
= 3; x
< SBR_NUM
; x
++)
330 // Set 4 bit values in a sparse bitmap. This allows a bitmap to
331 // function as a sparse array of 4 bit values.
332 // QUAD is the index, QUAD_VALUE is the 4 bit value to set.
335 sbr_sparse_bitmap::bitmap_set_quad (bitmap head
, int quad
, int quad_value
)
337 bitmap_set_aligned_chunk (head
, quad
, 4, (BITMAP_WORD
) quad_value
);
340 // Get a 4 bit value from a sparse bitmap. This allows a bitmap to
341 // function as a sparse array of 4 bit values.
342 // QUAD is the index.
344 sbr_sparse_bitmap::bitmap_get_quad (const_bitmap head
, int quad
)
346 return (int) bitmap_get_aligned_chunk (head
, quad
, 4);
349 // Set the range on entry to basic block BB to R.
352 sbr_sparse_bitmap::set_bb_range (const_basic_block bb
, const irange
&r
)
354 if (r
.undefined_p ())
356 bitmap_set_quad (bitvec
, bb
->index
, SBR_UNDEF
);
360 // Loop thru the values to see if R is already present.
361 for (int x
= 0; x
< SBR_NUM
; x
++)
362 if (!m_range
[x
] || r
== *(m_range
[x
]))
365 m_range
[x
] = m_irange_allocator
->allocate (r
);
366 bitmap_set_quad (bitvec
, bb
->index
, x
+ 1);
369 // All values are taken, default to VARYING.
370 bitmap_set_quad (bitvec
, bb
->index
, SBR_VARYING
);
374 // Return the range associated with block BB in R. Return false if
375 // there is no range.
378 sbr_sparse_bitmap::get_bb_range (irange
&r
, const_basic_block bb
)
380 int value
= bitmap_get_quad (bitvec
, bb
->index
);
385 gcc_checking_assert (value
<= SBR_UNDEF
);
386 if (value
== SBR_UNDEF
)
389 r
= *(m_range
[value
- 1]);
393 // Return true if a range is present.
396 sbr_sparse_bitmap::bb_range_p (const_basic_block bb
)
398 return (bitmap_get_quad (bitvec
, bb
->index
) != 0);
401 // -------------------------------------------------------------------------
403 // Initialize the block cache.
405 block_range_cache::block_range_cache ()
407 bitmap_obstack_initialize (&m_bitmaps
);
408 m_ssa_ranges
.create (0);
409 m_ssa_ranges
.safe_grow_cleared (num_ssa_names
);
410 m_irange_allocator
= new irange_allocator
;
413 // Remove any m_block_caches which have been created.
415 block_range_cache::~block_range_cache ()
417 delete m_irange_allocator
;
418 // Release the vector itself.
419 m_ssa_ranges
.release ();
420 bitmap_obstack_release (&m_bitmaps
);
423 // Set the range for NAME on entry to block BB to R.
424 // If it has not been accessed yet, allocate it first.
427 block_range_cache::set_bb_range (tree name
, const_basic_block bb
,
430 unsigned v
= SSA_NAME_VERSION (name
);
431 if (v
>= m_ssa_ranges
.length ())
432 m_ssa_ranges
.safe_grow_cleared (num_ssa_names
+ 1);
434 if (!m_ssa_ranges
[v
])
436 // Use sparse representation if there are too many basic blocks.
437 if (last_basic_block_for_fn (cfun
) > param_evrp_sparse_threshold
)
439 void *r
= m_irange_allocator
->get_memory (sizeof (sbr_sparse_bitmap
));
440 m_ssa_ranges
[v
] = new (r
) sbr_sparse_bitmap (TREE_TYPE (name
),
446 // Otherwise use the default vector implemntation.
447 void *r
= m_irange_allocator
->get_memory (sizeof (sbr_vector
));
448 m_ssa_ranges
[v
] = new (r
) sbr_vector (TREE_TYPE (name
),
452 return m_ssa_ranges
[v
]->set_bb_range (bb
, r
);
456 // Return a pointer to the ssa_block_cache for NAME. If it has not been
457 // accessed yet, return NULL.
459 inline ssa_block_ranges
*
460 block_range_cache::query_block_ranges (tree name
)
462 unsigned v
= SSA_NAME_VERSION (name
);
463 if (v
>= m_ssa_ranges
.length () || !m_ssa_ranges
[v
])
465 return m_ssa_ranges
[v
];
470 // Return the range for NAME on entry to BB in R. Return true if there
474 block_range_cache::get_bb_range (irange
&r
, tree name
, const_basic_block bb
)
476 ssa_block_ranges
*ptr
= query_block_ranges (name
);
478 return ptr
->get_bb_range (r
, bb
);
482 // Return true if NAME has a range set in block BB.
485 block_range_cache::bb_range_p (tree name
, const_basic_block bb
)
487 ssa_block_ranges
*ptr
= query_block_ranges (name
);
489 return ptr
->bb_range_p (bb
);
493 // Print all known block caches to file F.
496 block_range_cache::dump (FILE *f
)
499 for (x
= 0; x
< m_ssa_ranges
.length (); ++x
)
503 fprintf (f
, " Ranges for ");
504 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
506 m_ssa_ranges
[x
]->dump (f
);
512 // Print all known ranges on entry to blobk BB to file F.
515 block_range_cache::dump (FILE *f
, basic_block bb
, bool print_varying
)
519 bool summarize_varying
= false;
520 for (x
= 1; x
< m_ssa_ranges
.length (); ++x
)
522 if (!gimple_range_ssa_p (ssa_name (x
)))
524 if (m_ssa_ranges
[x
] && m_ssa_ranges
[x
]->get_bb_range (r
, bb
))
526 if (!print_varying
&& r
.varying_p ())
528 summarize_varying
= true;
531 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
537 // If there were any varying entries, lump them all together.
538 if (summarize_varying
)
540 fprintf (f
, "VARYING_P on entry : ");
541 for (x
= 1; x
< num_ssa_names
; ++x
)
543 if (!gimple_range_ssa_p (ssa_name (x
)))
545 if (m_ssa_ranges
[x
] && m_ssa_ranges
[x
]->get_bb_range (r
, bb
))
549 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
558 // -------------------------------------------------------------------------
560 // Initialize a global cache.
562 ssa_global_cache::ssa_global_cache ()
565 m_irange_allocator
= new irange_allocator
;
568 // Deconstruct a global cache.
570 ssa_global_cache::~ssa_global_cache ()
573 delete m_irange_allocator
;
576 // Retrieve the global range of NAME from cache memory if it exists.
577 // Return the value in R.
580 ssa_global_cache::get_global_range (irange
&r
, tree name
) const
582 unsigned v
= SSA_NAME_VERSION (name
);
583 if (v
>= m_tab
.length ())
586 irange
*stow
= m_tab
[v
];
593 // Set the range for NAME to R in the global cache.
594 // Return TRUE if there was already a range set, otherwise false.
597 ssa_global_cache::set_global_range (tree name
, const irange
&r
)
599 unsigned v
= SSA_NAME_VERSION (name
);
600 if (v
>= m_tab
.length ())
601 m_tab
.safe_grow_cleared (num_ssa_names
+ 1);
603 irange
*m
= m_tab
[v
];
604 if (m
&& m
->fits_p (r
))
607 m_tab
[v
] = m_irange_allocator
->allocate (r
);
611 // Set the range for NAME to R in the glonbal cache.
614 ssa_global_cache::clear_global_range (tree name
)
616 unsigned v
= SSA_NAME_VERSION (name
);
617 if (v
>= m_tab
.length ())
618 m_tab
.safe_grow_cleared (num_ssa_names
+ 1);
622 // Clear the global cache.
625 ssa_global_cache::clear ()
627 memset (m_tab
.address(), 0, m_tab
.length () * sizeof (irange
*));
630 // Dump the contents of the global cache to F.
633 ssa_global_cache::dump (FILE *f
)
635 /* Cleared after the table header has been printed. */
636 bool print_header
= true;
637 for (unsigned x
= 1; x
< num_ssa_names
; x
++)
640 if (gimple_range_ssa_p (ssa_name (x
)) &&
641 get_global_range (r
, ssa_name (x
)) && !r
.varying_p ())
645 /* Print the header only when there's something else
647 fprintf (f
, "Non-varying global ranges:\n");
648 fprintf (f
, "=========================:\n");
649 print_header
= false;
652 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
663 // --------------------------------------------------------------------------
666 // This class will manage the timestamps for each ssa_name.
667 // When a value is calculated, the timestamp is set to the current time.
668 // Current time is then incremented. Any dependencies will already have
669 // been calculated, and will thus have older timestamps.
670 // If one of those values is ever calculated again, it will get a newer
671 // timestamp, and the "current_p" check will fail.
678 bool current_p (tree name
, tree dep1
, tree dep2
) const;
679 void set_timestamp (tree name
);
680 void set_always_current (tree name
);
682 unsigned temporal_value (unsigned ssa
) const;
684 unsigned m_current_time
;
685 vec
<unsigned> m_timestamp
;
689 temporal_cache::temporal_cache ()
692 m_timestamp
.create (0);
693 m_timestamp
.safe_grow_cleared (num_ssa_names
);
697 temporal_cache::~temporal_cache ()
699 m_timestamp
.release ();
702 // Return the timestamp value for SSA, or 0 if there isnt one.
705 temporal_cache::temporal_value (unsigned ssa
) const
707 if (ssa
>= m_timestamp
.length ())
709 return m_timestamp
[ssa
];
712 // Return TRUE if the timestampe for NAME is newer than any of its dependents.
713 // Up to 2 dependencies can be checked.
716 temporal_cache::current_p (tree name
, tree dep1
, tree dep2
) const
718 unsigned ts
= temporal_value (SSA_NAME_VERSION (name
));
722 // Any non-registered dependencies will have a value of 0 and thus be older.
723 // Return true if time is newer than either dependent.
725 if (dep1
&& ts
< temporal_value (SSA_NAME_VERSION (dep1
)))
727 if (dep2
&& ts
< temporal_value (SSA_NAME_VERSION (dep2
)))
733 // This increments the global timer and sets the timestamp for NAME.
736 temporal_cache::set_timestamp (tree name
)
738 unsigned v
= SSA_NAME_VERSION (name
);
739 if (v
>= m_timestamp
.length ())
740 m_timestamp
.safe_grow_cleared (num_ssa_names
+ 20);
741 m_timestamp
[v
] = ++m_current_time
;
744 // Set the timestamp to 0, marking it as "always up to date".
747 temporal_cache::set_always_current (tree name
)
749 unsigned v
= SSA_NAME_VERSION (name
);
750 if (v
>= m_timestamp
.length ())
751 m_timestamp
.safe_grow_cleared (num_ssa_names
+ 20);
755 // --------------------------------------------------------------------------
757 // This class provides an abstraction of a list of blocks to be updated
758 // by the cache. It is currently a stack but could be changed. It also
759 // maintains a list of blocks which have failed propagation, and does not
760 // enter any of those blocks into the list.
762 // A vector over the BBs is maintained, and an entry of 0 means it is not in
763 // a list. Otherwise, the entry is the next block in the list. -1 terminates
764 // the list. m_head points to the top of the list, -1 if the list is empty.
771 void add (basic_block bb
);
773 inline bool empty_p () { return m_update_head
== -1; }
774 inline void clear_failures () { bitmap_clear (m_propfail
); }
775 inline void propagation_failed (basic_block bb
)
776 { bitmap_set_bit (m_propfail
, bb
->index
); }
778 vec
<int> m_update_list
;
783 // Create an update list.
785 update_list::update_list ()
787 m_update_list
.create (0);
788 m_update_list
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 64);
790 m_propfail
= BITMAP_ALLOC (NULL
);
793 // Destroy an update list.
795 update_list::~update_list ()
797 m_update_list
.release ();
798 BITMAP_FREE (m_propfail
);
801 // Add BB to the list of blocks to update, unless it's already in the list.
804 update_list::add (basic_block bb
)
807 // If propagation has failed for BB, or its already in the list, don't
809 if ((unsigned)i
>= m_update_list
.length ())
810 m_update_list
.safe_grow_cleared (i
+ 64);
811 if (!m_update_list
[i
] && !bitmap_bit_p (m_propfail
, i
))
816 m_update_list
[i
] = -1;
820 gcc_checking_assert (m_update_head
> 0);
821 m_update_list
[i
] = m_update_head
;
827 // Remove a block from the list.
832 gcc_checking_assert (!empty_p ());
833 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, m_update_head
);
834 int pop
= m_update_head
;
835 m_update_head
= m_update_list
[pop
];
836 m_update_list
[pop
] = 0;
840 // --------------------------------------------------------------------------
842 ranger_cache::ranger_cache (int not_executable_flag
)
843 : m_gori (not_executable_flag
)
845 m_workback
.create (0);
846 m_workback
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
847 m_temporal
= new temporal_cache
;
848 // If DOM info is available, spawn an oracle as well.
849 if (dom_info_available_p (CDI_DOMINATORS
))
850 m_oracle
= new dom_oracle ();
854 unsigned x
, lim
= last_basic_block_for_fn (cfun
);
855 // Calculate outgoing range info upfront. This will fully populate the
856 // m_maybe_variant bitmap which will help eliminate processing of names
857 // which never have their ranges adjusted.
858 for (x
= 0; x
< lim
; x
++)
860 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, x
);
864 m_update
= new update_list ();
867 ranger_cache::~ranger_cache ()
873 m_workback
.release ();
876 // Dump the global caches to file F. if GORI_DUMP is true, dump the
880 ranger_cache::dump (FILE *f
)
886 // Dump the caches for basic block BB to file F.
889 ranger_cache::dump_bb (FILE *f
, basic_block bb
)
891 m_gori
.gori_map::dump (f
, bb
, false);
892 m_on_entry
.dump (f
, bb
);
894 m_oracle
->dump (f
, bb
);
897 // Get the global range for NAME, and return in R. Return false if the
898 // global range is not set.
901 ranger_cache::get_global_range (irange
&r
, tree name
) const
903 return m_globals
.get_global_range (r
, name
);
906 // Get the global range for NAME, and return in R if the value is not stale.
907 // If the range is set, but is stale, mark it current and return false.
908 // If it is not set pick up the legacy global value, mark it current, and
910 // Note there is always a value returned in R. The return value indicates
911 // whether that value is an up-to-date calculated value or not..
914 ranger_cache::get_non_stale_global_range (irange
&r
, tree name
)
916 if (m_globals
.get_global_range (r
, name
))
918 // Use this value if the range is constant or current.
920 || m_temporal
->current_p (name
, m_gori
.depend1 (name
),
921 m_gori
.depend2 (name
)))
926 // Global has never been accessed, so pickup the legacy global value.
927 r
= gimple_range_global (name
);
928 m_globals
.set_global_range (name
, r
);
930 // After a stale check failure, mark the value as always current until a
932 m_temporal
->set_always_current (name
);
935 // Set the global range of NAME to R.
938 ranger_cache::set_global_range (tree name
, const irange
&r
)
940 if (m_globals
.set_global_range (name
, r
))
942 // If there was already a range set, propagate the new value.
943 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
945 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
947 if (DEBUG_RANGE_CACHE
)
948 fprintf (dump_file
, " GLOBAL :");
950 propagate_updated_value (name
, bb
);
952 // Constants no longer need to tracked. Any further refinement has to be
953 // undefined. Propagation works better with constants. PR 100512.
954 // Pointers which resolve to non-zero also do not need
955 // tracking in the cache as they will never change. See PR 98866.
956 // Timestamp must always be updated, or dependent calculations may
957 // not include this latest value. PR 100774.
960 || (POINTER_TYPE_P (TREE_TYPE (name
)) && r
.nonzero_p ()))
961 m_gori
.set_range_invariant (name
);
962 m_temporal
->set_timestamp (name
);
965 // Provide lookup for the gori-computes class to access the best known range
966 // of an ssa_name in any given basic block. Note, this does no additonal
967 // lookups, just accesses the data that is already known.
969 // Get the range of NAME when the def occurs in block BB. If BB is NULL
970 // get the best global value available.
973 ranger_cache::range_of_def (irange
&r
, tree name
, basic_block bb
)
975 gcc_checking_assert (gimple_range_ssa_p (name
));
976 gcc_checking_assert (!bb
|| bb
== gimple_bb (SSA_NAME_DEF_STMT (name
)));
978 // Pick up the best global range available.
979 if (!m_globals
.get_global_range (r
, name
))
981 // If that fails, try to calculate the range using just global values.
982 gimple
*s
= SSA_NAME_DEF_STMT (name
);
983 if (gimple_get_lhs (s
) == name
)
984 fold_range (r
, s
, get_global_range_query ());
986 r
= gimple_range_global (name
);
990 m_non_null
.adjust_range (r
, name
, bb
, false);
993 // Get the range of NAME as it occurs on entry to block BB.
996 ranger_cache::entry_range (irange
&r
, tree name
, basic_block bb
)
998 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1000 r
= gimple_range_global (name
);
1004 // Look for the on-entry value of name in BB from the cache.
1005 // Otherwise pick up the best available global value.
1006 if (!m_on_entry
.get_bb_range (r
, name
, bb
))
1007 range_of_def (r
, name
);
1009 m_non_null
.adjust_range (r
, name
, bb
, false);
1012 // Get the range of NAME as it occurs on exit from block BB.
1015 ranger_cache::exit_range (irange
&r
, tree name
, basic_block bb
)
1017 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1019 r
= gimple_range_global (name
);
1023 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1024 basic_block def_bb
= gimple_bb (s
);
1026 range_of_def (r
, name
, bb
);
1028 entry_range (r
, name
, bb
);
1032 // Implement range_of_expr.
1035 ranger_cache::range_of_expr (irange
&r
, tree name
, gimple
*stmt
)
1037 if (!gimple_range_ssa_p (name
))
1039 get_tree_range (r
, name
, stmt
);
1043 basic_block bb
= gimple_bb (stmt
);
1044 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1045 basic_block def_bb
= gimple_bb (def_stmt
);
1048 range_of_def (r
, name
, bb
);
1050 entry_range (r
, name
, bb
);
1055 // Implement range_on_edge. Always return the best available range.
1058 ranger_cache::range_on_edge (irange
&r
, edge e
, tree expr
)
1060 if (gimple_range_ssa_p (expr
))
1062 exit_range (r
, expr
, e
->src
);
1063 int_range_max edge_range
;
1064 if (m_gori
.outgoing_edge_range_p (edge_range
, e
, expr
, *this))
1065 r
.intersect (edge_range
);
1069 return get_tree_range (r
, expr
, NULL
);
1073 // Return a static range for NAME on entry to basic block BB in R. If
1074 // calc is true, fill any cache entries required between BB and the
1075 // def block for NAME. Otherwise, return false if the cache is empty.
1078 ranger_cache::block_range (irange
&r
, basic_block bb
, tree name
, bool calc
)
1080 gcc_checking_assert (gimple_range_ssa_p (name
));
1082 // If there are no range calculations anywhere in the IL, global range
1083 // applies everywhere, so don't bother caching it.
1084 if (!m_gori
.has_edge_range_p (name
))
1089 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1090 basic_block def_bb
= NULL
;
1092 def_bb
= gimple_bb (def_stmt
);;
1095 // If we get to the entry block, this better be a default def
1096 // or range_on_entry was called for a block not dominated by
1098 gcc_checking_assert (SSA_NAME_IS_DEFAULT_DEF (name
));
1099 def_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1102 // There is no range on entry for the definition block.
1106 // Otherwise, go figure out what is known in predecessor blocks.
1107 fill_block_cache (name
, bb
, def_bb
);
1108 gcc_checking_assert (m_on_entry
.bb_range_p (name
, bb
));
1110 return m_on_entry
.get_bb_range (r
, name
, bb
);
1113 // If there is anything in the propagation update_list, continue
1114 // processing NAME until the list of blocks is empty.
1117 ranger_cache::propagate_cache (tree name
)
1122 int_range_max new_range
;
1123 int_range_max current_range
;
1124 int_range_max e_range
;
1126 // Process each block by seeing if its calculated range on entry is
1127 // the same as its cached value. If there is a difference, update
1128 // the cache to reflect the new value, and check to see if any
1129 // successors have cache entries which may need to be checked for
1132 while (!m_update
->empty_p ())
1134 bb
= m_update
->pop ();
1135 gcc_checking_assert (m_on_entry
.bb_range_p (name
, bb
));
1136 m_on_entry
.get_bb_range (current_range
, name
, bb
);
1138 if (DEBUG_RANGE_CACHE
)
1140 fprintf (dump_file
, "FWD visiting block %d for ", bb
->index
);
1141 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1142 fprintf (dump_file
, " starting range : ");
1143 current_range
.dump (dump_file
);
1144 fprintf (dump_file
, "\n");
1147 // Calculate the "new" range on entry by unioning the pred edges.
1148 new_range
.set_undefined ();
1149 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1151 range_on_edge (e_range
, e
, name
);
1152 if (DEBUG_RANGE_CACHE
)
1154 fprintf (dump_file
, " edge %d->%d :", e
->src
->index
, bb
->index
);
1155 e_range
.dump (dump_file
);
1156 fprintf (dump_file
, "\n");
1158 new_range
.union_ (e_range
);
1159 if (new_range
.varying_p ())
1163 // If the range on entry has changed, update it.
1164 if (new_range
!= current_range
)
1166 bool ok_p
= m_on_entry
.set_bb_range (name
, bb
, new_range
);
1167 // If the cache couldn't set the value, mark it as failed.
1169 m_update
->propagation_failed (bb
);
1170 if (DEBUG_RANGE_CACHE
)
1174 fprintf (dump_file
, " Cache failure to store value:");
1175 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1176 fprintf (dump_file
, " ");
1180 fprintf (dump_file
, " Updating range to ");
1181 new_range
.dump (dump_file
);
1183 fprintf (dump_file
, "\n Updating blocks :");
1185 // Mark each successor that has a range to re-check its range
1186 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1187 if (m_on_entry
.bb_range_p (name
, e
->dest
))
1189 if (DEBUG_RANGE_CACHE
)
1190 fprintf (dump_file
, " bb%d",e
->dest
->index
);
1191 m_update
->add (e
->dest
);
1193 if (DEBUG_RANGE_CACHE
)
1194 fprintf (dump_file
, "\n");
1197 if (DEBUG_RANGE_CACHE
)
1199 fprintf (dump_file
, "DONE visiting blocks for ");
1200 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1201 fprintf (dump_file
, "\n");
1203 m_update
->clear_failures ();
1206 // Check to see if an update to the value for NAME in BB has any effect
1207 // on values already in the on-entry cache for successor blocks.
1208 // If it does, update them. Don't visit any blocks which dont have a cache
1212 ranger_cache::propagate_updated_value (tree name
, basic_block bb
)
1217 // The update work list should be empty at this point.
1218 gcc_checking_assert (m_update
->empty_p ());
1219 gcc_checking_assert (bb
);
1221 if (DEBUG_RANGE_CACHE
)
1223 fprintf (dump_file
, " UPDATE cache for ");
1224 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1225 fprintf (dump_file
, " in BB %d : successors : ", bb
->index
);
1227 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1229 // Only update active cache entries.
1230 if (m_on_entry
.bb_range_p (name
, e
->dest
))
1232 m_update
->add (e
->dest
);
1233 if (DEBUG_RANGE_CACHE
)
1234 fprintf (dump_file
, " UPDATE: bb%d", e
->dest
->index
);
1237 if (!m_update
->empty_p ())
1239 if (DEBUG_RANGE_CACHE
)
1240 fprintf (dump_file
, "\n");
1241 propagate_cache (name
);
1245 if (DEBUG_RANGE_CACHE
)
1246 fprintf (dump_file
, " : No updates!\n");
1250 // Make sure that the range-on-entry cache for NAME is set for block BB.
1251 // Work back through the CFG to DEF_BB ensuring the range is calculated
1252 // on the block/edges leading back to that point.
1255 ranger_cache::fill_block_cache (tree name
, basic_block bb
, basic_block def_bb
)
1259 int_range_max block_result
;
1260 int_range_max undefined
;
1262 // At this point we shouldn't be looking at the def, entry or exit block.
1263 gcc_checking_assert (bb
!= def_bb
&& bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
1264 bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1266 // If the block cache is set, then we've already visited this block.
1267 if (m_on_entry
.bb_range_p (name
, bb
))
1270 // Visit each block back to the DEF. Initialize each one to UNDEFINED.
1271 // m_visited at the end will contain all the blocks that we needed to set
1272 // the range_on_entry cache for.
1273 m_workback
.truncate (0);
1274 m_workback
.quick_push (bb
);
1275 undefined
.set_undefined ();
1276 m_on_entry
.set_bb_range (name
, bb
, undefined
);
1277 gcc_checking_assert (m_update
->empty_p ());
1279 if (DEBUG_RANGE_CACHE
)
1281 fprintf (dump_file
, "\n");
1282 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1283 fprintf (dump_file
, " : ");
1286 while (m_workback
.length () > 0)
1288 basic_block node
= m_workback
.pop ();
1289 if (DEBUG_RANGE_CACHE
)
1291 fprintf (dump_file
, "BACK visiting block %d for ", node
->index
);
1292 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1293 fprintf (dump_file
, "\n");
1296 FOR_EACH_EDGE (e
, ei
, node
->preds
)
1298 basic_block pred
= e
->src
;
1301 if (DEBUG_RANGE_CACHE
)
1302 fprintf (dump_file
, " %d->%d ",e
->src
->index
, e
->dest
->index
);
1304 // If the pred block is the def block add this BB to update list.
1307 m_update
->add (node
);
1311 // If the pred is entry but NOT def, then it is used before
1312 // defined, it'll get set to [] and no need to update it.
1313 if (pred
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1315 if (DEBUG_RANGE_CACHE
)
1316 fprintf (dump_file
, "entry: bail.");
1320 // Regardless of whether we have visited pred or not, if the
1321 // pred has a non-null reference, revisit this block.
1322 // Don't search the DOM tree.
1323 if (m_non_null
.non_null_deref_p (name
, pred
, false))
1325 if (DEBUG_RANGE_CACHE
)
1326 fprintf (dump_file
, "nonnull: update ");
1327 m_update
->add (node
);
1330 // If the pred block already has a range, or if it can contribute
1331 // something new. Ie, the edge generates a range of some sort.
1332 if (m_on_entry
.get_bb_range (r
, name
, pred
))
1334 if (DEBUG_RANGE_CACHE
)
1336 fprintf (dump_file
, "has cache, ");
1338 fprintf (dump_file
, ", ");
1340 if (!r
.undefined_p () || m_gori
.has_edge_range_p (name
, e
))
1342 m_update
->add (node
);
1343 if (DEBUG_RANGE_CACHE
)
1344 fprintf (dump_file
, "update. ");
1349 if (DEBUG_RANGE_CACHE
)
1350 fprintf (dump_file
, "pushing undefined pred block.\n");
1351 // If the pred hasn't been visited (has no range), add it to
1353 gcc_checking_assert (!m_on_entry
.bb_range_p (name
, pred
));
1354 m_on_entry
.set_bb_range (name
, pred
, undefined
);
1355 m_workback
.quick_push (pred
);
1359 if (DEBUG_RANGE_CACHE
)
1360 fprintf (dump_file
, "\n");
1362 // Now fill in the marked blocks with values.
1363 propagate_cache (name
);
1364 if (DEBUG_RANGE_CACHE
)
1365 fprintf (dump_file
, " Propagation update done.\n");