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 && (param_evrp_mode & EVRP_MODE_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
);
67 if (bitmap_bit_p (m_nn
[v
], bb
->index
))
70 // See if any dominator has set non-zero.
71 if (search_dom
&& dom_info_available_p (CDI_DOMINATORS
))
73 // Search back to the Def block, or the top, whichever is closer.
74 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
75 basic_block def_dom
= def_bb
76 ? get_immediate_dominator (CDI_DOMINATORS
, def_bb
)
80 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
81 if (bitmap_bit_p (m_nn
[v
], bb
->index
))
87 // If NAME has a non-null dereference in block BB, adjust R with the
88 // non-zero information from non_null_deref_p, and return TRUE. If
89 // SEARCH_DOM is true, non_null_deref_p should search the dominator tree.
92 non_null_ref::adjust_range (irange
&r
, tree name
, basic_block bb
,
95 // Non-call exceptions mean we could throw in the middle of the
96 // block, so just punt on those for now.
97 if (cfun
->can_throw_non_call_exceptions
)
100 // We only care about the null / non-null property of pointers.
101 if (!POINTER_TYPE_P (TREE_TYPE (name
)) || r
.zero_p () || r
.nonzero_p ())
104 // Check if pointers have any non-null dereferences.
105 if (non_null_deref_p (name
, bb
, search_dom
))
108 nz
.set_nonzero (TREE_TYPE (name
));
115 // Allocate an populate the bitmap for NAME. An ON bit for a block
116 // index indicates there is a non-null reference in that block. In
117 // order to populate the bitmap, a quick run of all the immediate uses
118 // are made and the statement checked to see if a non-null dereference
119 // is made on that statement.
122 non_null_ref::process_name (tree name
)
124 unsigned v
= SSA_NAME_VERSION (name
);
126 imm_use_iterator iter
;
129 // Only tracked for pointers.
130 if (!POINTER_TYPE_P (TREE_TYPE (name
)))
133 // Already processed if a bitmap has been allocated.
137 b
= BITMAP_ALLOC (&m_bitmaps
);
139 // Loop over each immediate use and see if it implies a non-null value.
140 FOR_EACH_IMM_USE_FAST (use_p
, iter
, name
)
142 gimple
*s
= USE_STMT (use_p
);
143 unsigned index
= gimple_bb (s
)->index
;
145 // If bit is already set for this block, dont bother looking again.
146 if (bitmap_bit_p (b
, index
))
149 // If we can infer a nonnull range, then set the bit for this BB
150 if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name
)
151 && infer_nonnull_range (s
, name
))
152 bitmap_set_bit (b
, index
);
158 // -------------------------------------------------------------------------
160 // This class represents the API into a cache of ranges for an SSA_NAME.
161 // Routines must be implemented to set, get, and query if a value is set.
163 class ssa_block_ranges
166 virtual bool set_bb_range (const_basic_block bb
, const irange
&r
) = 0;
167 virtual bool get_bb_range (irange
&r
, const_basic_block bb
) = 0;
168 virtual bool bb_range_p (const_basic_block bb
) = 0;
173 // Print the list of known ranges for file F in a nice format.
176 ssa_block_ranges::dump (FILE *f
)
181 FOR_EACH_BB_FN (bb
, cfun
)
182 if (get_bb_range (r
, bb
))
184 fprintf (f
, "BB%d -> ", bb
->index
);
190 // This class implements the range cache as a linear vector, indexed by BB.
191 // It caches a varying and undefined range which are used instead of
192 // allocating new ones each time.
194 class sbr_vector
: public ssa_block_ranges
197 sbr_vector (tree t
, irange_allocator
*allocator
);
199 virtual bool set_bb_range (const_basic_block bb
, const irange
&r
) OVERRIDE
;
200 virtual bool get_bb_range (irange
&r
, const_basic_block bb
) OVERRIDE
;
201 virtual bool bb_range_p (const_basic_block bb
) OVERRIDE
;
203 irange
**m_tab
; // Non growing vector.
205 int_range
<2> m_varying
;
206 int_range
<2> m_undefined
;
208 irange_allocator
*m_irange_allocator
;
212 // Initialize a block cache for an ssa_name of type T.
214 sbr_vector::sbr_vector (tree t
, irange_allocator
*allocator
)
216 gcc_checking_assert (TYPE_P (t
));
218 m_irange_allocator
= allocator
;
219 m_tab_size
= last_basic_block_for_fn (cfun
) + 1;
220 m_tab
= (irange
**)allocator
->get_memory (m_tab_size
* sizeof (irange
*));
221 memset (m_tab
, 0, m_tab_size
* sizeof (irange
*));
223 // Create the cached type range.
224 m_varying
.set_varying (t
);
225 m_undefined
.set_undefined ();
228 // Set the range for block BB to be R.
231 sbr_vector::set_bb_range (const_basic_block bb
, const irange
&r
)
234 gcc_checking_assert (bb
->index
< m_tab_size
);
237 else if (r
.undefined_p ())
240 m
= m_irange_allocator
->allocate (r
);
241 m_tab
[bb
->index
] = m
;
245 // Return the range associated with block BB in R. Return false if
246 // there is no range.
249 sbr_vector::get_bb_range (irange
&r
, const_basic_block bb
)
251 gcc_checking_assert (bb
->index
< m_tab_size
);
252 irange
*m
= m_tab
[bb
->index
];
261 // Return true if a range is present.
264 sbr_vector::bb_range_p (const_basic_block bb
)
266 gcc_checking_assert (bb
->index
< m_tab_size
);
267 return m_tab
[bb
->index
] != NULL
;
270 // This class implements the on entry cache via a sparse bitmap.
271 // It uses the quad bit routines to access 4 bits at a time.
272 // A value of 0 (the default) means there is no entry, and a value of
273 // 1 thru SBR_NUM represents an element in the m_range vector.
274 // Varying is given the first value (1) and pre-cached.
275 // SBR_NUM + 1 represents the value of UNDEFINED, and is never stored.
276 // SBR_NUM is the number of values that can be cached.
277 // Indexes are 1..SBR_NUM and are stored locally at m_range[0..SBR_NUM-1]
280 #define SBR_UNDEF SBR_NUM + 1
281 #define SBR_VARYING 1
283 class sbr_sparse_bitmap
: public ssa_block_ranges
286 sbr_sparse_bitmap (tree t
, irange_allocator
*allocator
, bitmap_obstack
*bm
);
287 virtual bool set_bb_range (const_basic_block bb
, const irange
&r
) OVERRIDE
;
288 virtual bool get_bb_range (irange
&r
, const_basic_block bb
) OVERRIDE
;
289 virtual bool bb_range_p (const_basic_block bb
) OVERRIDE
;
291 void bitmap_set_quad (bitmap head
, int quad
, int quad_value
);
292 int bitmap_get_quad (const_bitmap head
, int quad
);
293 irange_allocator
*m_irange_allocator
;
294 irange
*m_range
[SBR_NUM
];
299 // Initialize a block cache for an ssa_name of type T.
301 sbr_sparse_bitmap::sbr_sparse_bitmap (tree t
, irange_allocator
*allocator
,
304 gcc_checking_assert (TYPE_P (t
));
306 bitvec
= BITMAP_ALLOC (bm
);
307 m_irange_allocator
= allocator
;
308 // Pre-cache varying.
309 m_range
[0] = m_irange_allocator
->allocate (2);
310 m_range
[0]->set_varying (t
);
311 // Pre-cache zero and non-zero values for pointers.
312 if (POINTER_TYPE_P (t
))
314 m_range
[1] = m_irange_allocator
->allocate (2);
315 m_range
[1]->set_nonzero (t
);
316 m_range
[2] = m_irange_allocator
->allocate (2);
317 m_range
[2]->set_zero (t
);
320 m_range
[1] = m_range
[2] = NULL
;
321 // Clear SBR_NUM entries.
322 for (int x
= 3; x
< SBR_NUM
; x
++)
326 // Set 4 bit values in a sparse bitmap. This allows a bitmap to
327 // function as a sparse array of 4 bit values.
328 // QUAD is the index, QUAD_VALUE is the 4 bit value to set.
331 sbr_sparse_bitmap::bitmap_set_quad (bitmap head
, int quad
, int quad_value
)
333 bitmap_set_aligned_chunk (head
, quad
, 4, (BITMAP_WORD
) quad_value
);
336 // Get a 4 bit value from a sparse bitmap. This allows a bitmap to
337 // function as a sparse array of 4 bit values.
338 // QUAD is the index.
340 sbr_sparse_bitmap::bitmap_get_quad (const_bitmap head
, int quad
)
342 return (int) bitmap_get_aligned_chunk (head
, quad
, 4);
345 // Set the range on entry to basic block BB to R.
348 sbr_sparse_bitmap::set_bb_range (const_basic_block bb
, const irange
&r
)
350 if (r
.undefined_p ())
352 bitmap_set_quad (bitvec
, bb
->index
, SBR_UNDEF
);
356 // Loop thru the values to see if R is already present.
357 for (int x
= 0; x
< SBR_NUM
; x
++)
358 if (!m_range
[x
] || r
== *(m_range
[x
]))
361 m_range
[x
] = m_irange_allocator
->allocate (r
);
362 bitmap_set_quad (bitvec
, bb
->index
, x
+ 1);
365 // All values are taken, default to VARYING.
366 bitmap_set_quad (bitvec
, bb
->index
, SBR_VARYING
);
370 // Return the range associated with block BB in R. Return false if
371 // there is no range.
374 sbr_sparse_bitmap::get_bb_range (irange
&r
, const_basic_block bb
)
376 int value
= bitmap_get_quad (bitvec
, bb
->index
);
381 gcc_checking_assert (value
<= SBR_UNDEF
);
382 if (value
== SBR_UNDEF
)
385 r
= *(m_range
[value
- 1]);
389 // Return true if a range is present.
392 sbr_sparse_bitmap::bb_range_p (const_basic_block bb
)
394 return (bitmap_get_quad (bitvec
, bb
->index
) != 0);
397 // -------------------------------------------------------------------------
399 // Initialize the block cache.
401 block_range_cache::block_range_cache ()
403 bitmap_obstack_initialize (&m_bitmaps
);
404 m_ssa_ranges
.create (0);
405 m_ssa_ranges
.safe_grow_cleared (num_ssa_names
);
406 m_irange_allocator
= new irange_allocator
;
409 // Remove any m_block_caches which have been created.
411 block_range_cache::~block_range_cache ()
413 delete m_irange_allocator
;
414 // Release the vector itself.
415 m_ssa_ranges
.release ();
416 bitmap_obstack_release (&m_bitmaps
);
419 // Set the range for NAME on entry to block BB to R.
420 // If it has not been accessed yet, allocate it first.
423 block_range_cache::set_bb_range (tree name
, const_basic_block bb
,
426 unsigned v
= SSA_NAME_VERSION (name
);
427 if (v
>= m_ssa_ranges
.length ())
428 m_ssa_ranges
.safe_grow_cleared (num_ssa_names
+ 1);
430 if (!m_ssa_ranges
[v
])
432 // Use sparse representation if there are too many basic blocks.
433 if (last_basic_block_for_fn (cfun
) > param_evrp_sparse_threshold
)
435 void *r
= m_irange_allocator
->get_memory (sizeof (sbr_sparse_bitmap
));
436 m_ssa_ranges
[v
] = new (r
) sbr_sparse_bitmap (TREE_TYPE (name
),
442 // Otherwise use the default vector implemntation.
443 void *r
= m_irange_allocator
->get_memory (sizeof (sbr_vector
));
444 m_ssa_ranges
[v
] = new (r
) sbr_vector (TREE_TYPE (name
),
448 return m_ssa_ranges
[v
]->set_bb_range (bb
, r
);
452 // Return a pointer to the ssa_block_cache for NAME. If it has not been
453 // accessed yet, return NULL.
455 inline ssa_block_ranges
*
456 block_range_cache::query_block_ranges (tree name
)
458 unsigned v
= SSA_NAME_VERSION (name
);
459 if (v
>= m_ssa_ranges
.length () || !m_ssa_ranges
[v
])
461 return m_ssa_ranges
[v
];
466 // Return the range for NAME on entry to BB in R. Return true if there
470 block_range_cache::get_bb_range (irange
&r
, tree name
, const_basic_block bb
)
472 ssa_block_ranges
*ptr
= query_block_ranges (name
);
474 return ptr
->get_bb_range (r
, bb
);
478 // Return true if NAME has a range set in block BB.
481 block_range_cache::bb_range_p (tree name
, const_basic_block bb
)
483 ssa_block_ranges
*ptr
= query_block_ranges (name
);
485 return ptr
->bb_range_p (bb
);
489 // Print all known block caches to file F.
492 block_range_cache::dump (FILE *f
)
495 for (x
= 0; x
< m_ssa_ranges
.length (); ++x
)
499 fprintf (f
, " Ranges for ");
500 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
502 m_ssa_ranges
[x
]->dump (f
);
508 // Print all known ranges on entry to blobk BB to file F.
511 block_range_cache::dump (FILE *f
, basic_block bb
, bool print_varying
)
515 bool summarize_varying
= false;
516 for (x
= 1; x
< m_ssa_ranges
.length (); ++x
)
518 if (!gimple_range_ssa_p (ssa_name (x
)))
520 if (m_ssa_ranges
[x
] && m_ssa_ranges
[x
]->get_bb_range (r
, bb
))
522 if (!print_varying
&& r
.varying_p ())
524 summarize_varying
= true;
527 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
533 // If there were any varying entries, lump them all together.
534 if (summarize_varying
)
536 fprintf (f
, "VARYING_P on entry : ");
537 for (x
= 1; x
< num_ssa_names
; ++x
)
539 if (!gimple_range_ssa_p (ssa_name (x
)))
541 if (m_ssa_ranges
[x
] && m_ssa_ranges
[x
]->get_bb_range (r
, bb
))
545 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
554 // -------------------------------------------------------------------------
556 // Initialize a global cache.
558 ssa_global_cache::ssa_global_cache ()
561 m_irange_allocator
= new irange_allocator
;
564 // Deconstruct a global cache.
566 ssa_global_cache::~ssa_global_cache ()
569 delete m_irange_allocator
;
572 // Retrieve the global range of NAME from cache memory if it exists.
573 // Return the value in R.
576 ssa_global_cache::get_global_range (irange
&r
, tree name
) const
578 unsigned v
= SSA_NAME_VERSION (name
);
579 if (v
>= m_tab
.length ())
582 irange
*stow
= m_tab
[v
];
589 // Set the range for NAME to R in the global cache.
590 // Return TRUE if there was already a range set, otherwise false.
593 ssa_global_cache::set_global_range (tree name
, const irange
&r
)
595 unsigned v
= SSA_NAME_VERSION (name
);
596 if (v
>= m_tab
.length ())
597 m_tab
.safe_grow_cleared (num_ssa_names
+ 1);
599 irange
*m
= m_tab
[v
];
600 if (m
&& m
->fits_p (r
))
603 m_tab
[v
] = m_irange_allocator
->allocate (r
);
607 // Set the range for NAME to R in the glonbal cache.
610 ssa_global_cache::clear_global_range (tree name
)
612 unsigned v
= SSA_NAME_VERSION (name
);
613 if (v
>= m_tab
.length ())
614 m_tab
.safe_grow_cleared (num_ssa_names
+ 1);
618 // Clear the global cache.
621 ssa_global_cache::clear ()
623 memset (m_tab
.address(), 0, m_tab
.length () * sizeof (irange
*));
626 // Dump the contents of the global cache to F.
629 ssa_global_cache::dump (FILE *f
)
631 /* Cleared after the table header has been printed. */
632 bool print_header
= true;
633 for (unsigned x
= 1; x
< num_ssa_names
; x
++)
636 if (gimple_range_ssa_p (ssa_name (x
)) &&
637 get_global_range (r
, ssa_name (x
)) && !r
.varying_p ())
641 /* Print the header only when there's something else
643 fprintf (f
, "Non-varying global ranges:\n");
644 fprintf (f
, "=========================:\n");
645 print_header
= false;
648 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
659 // --------------------------------------------------------------------------
662 // This class will manage the timestamps for each ssa_name.
663 // When a value is calculated, the timestamp is set to the current time.
664 // Current time is then incremented. Any dependencies will already have
665 // been calculated, and will thus have older timestamps.
666 // If one of those values is ever calculated again, it will get a newer
667 // timestamp, and the "current_p" check will fail.
674 bool current_p (tree name
, tree dep1
, tree dep2
) const;
675 void set_timestamp (tree name
);
676 void set_always_current (tree name
);
678 unsigned temporal_value (unsigned ssa
) const;
680 unsigned m_current_time
;
681 vec
<unsigned> m_timestamp
;
685 temporal_cache::temporal_cache ()
688 m_timestamp
.create (0);
689 m_timestamp
.safe_grow_cleared (num_ssa_names
);
693 temporal_cache::~temporal_cache ()
695 m_timestamp
.release ();
698 // Return the timestamp value for SSA, or 0 if there isnt one.
701 temporal_cache::temporal_value (unsigned ssa
) const
703 if (ssa
>= m_timestamp
.length ())
705 return m_timestamp
[ssa
];
708 // Return TRUE if the timestampe for NAME is newer than any of its dependents.
709 // Up to 2 dependencies can be checked.
712 temporal_cache::current_p (tree name
, tree dep1
, tree dep2
) const
714 unsigned ts
= temporal_value (SSA_NAME_VERSION (name
));
718 // Any non-registered dependencies will have a value of 0 and thus be older.
719 // Return true if time is newer than either dependent.
721 if (dep1
&& ts
< temporal_value (SSA_NAME_VERSION (dep1
)))
723 if (dep2
&& ts
< temporal_value (SSA_NAME_VERSION (dep2
)))
729 // This increments the global timer and sets the timestamp for NAME.
732 temporal_cache::set_timestamp (tree name
)
734 unsigned v
= SSA_NAME_VERSION (name
);
735 if (v
>= m_timestamp
.length ())
736 m_timestamp
.safe_grow_cleared (num_ssa_names
+ 20);
737 m_timestamp
[v
] = ++m_current_time
;
740 // Set the timestamp to 0, marking it as "always up to date".
743 temporal_cache::set_always_current (tree name
)
745 unsigned v
= SSA_NAME_VERSION (name
);
746 if (v
>= m_timestamp
.length ())
747 m_timestamp
.safe_grow_cleared (num_ssa_names
+ 20);
751 // --------------------------------------------------------------------------
753 ranger_cache::ranger_cache (int not_executable_flag
)
754 : m_gori (not_executable_flag
)
756 m_workback
.create (0);
757 m_workback
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
758 m_update_list
.create (0);
759 m_update_list
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
760 m_update_list
.truncate (0);
761 m_temporal
= new temporal_cache
;
762 // If DOM info is available, spawn an oracle as well.
763 if (dom_info_available_p (CDI_DOMINATORS
))
764 m_oracle
= new dom_oracle ();
768 unsigned x
, lim
= last_basic_block_for_fn (cfun
);
769 // Calculate outgoing range info upfront. This will fully populate the
770 // m_maybe_variant bitmap which will help eliminate processing of names
771 // which never have their ranges adjusted.
772 for (x
= 0; x
< lim
; x
++)
774 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, x
);
778 m_propfail
= BITMAP_ALLOC (NULL
);
781 ranger_cache::~ranger_cache ()
783 BITMAP_FREE (m_propfail
);
787 m_workback
.release ();
788 m_update_list
.release ();
791 // Dump the global caches to file F. if GORI_DUMP is true, dump the
795 ranger_cache::dump (FILE *f
)
801 // Dump the caches for basic block BB to file F.
804 ranger_cache::dump_bb (FILE *f
, basic_block bb
)
806 m_gori
.gori_map::dump (f
, bb
, false);
807 m_on_entry
.dump (f
, bb
);
809 m_oracle
->dump (f
, bb
);
812 // Get the global range for NAME, and return in R. Return false if the
813 // global range is not set.
816 ranger_cache::get_global_range (irange
&r
, tree name
) const
818 return m_globals
.get_global_range (r
, name
);
821 // Get the global range for NAME, and return in R if the value is not stale.
822 // If the range is set, but is stale, mark it current and return false.
823 // If it is not set pick up the legacy global value, mark it current, and
825 // Note there is always a value returned in R. The return value indicates
826 // whether that value is an up-to-date calculated value or not..
829 ranger_cache::get_non_stale_global_range (irange
&r
, tree name
)
831 if (m_globals
.get_global_range (r
, name
))
833 // Use this value if the range is constant or current.
835 || m_temporal
->current_p (name
, m_gori
.depend1 (name
),
836 m_gori
.depend2 (name
)))
841 // Global has never been accessed, so pickup the legacy global value.
842 r
= gimple_range_global (name
);
843 m_globals
.set_global_range (name
, r
);
845 // After a stale check failure, mark the value as always current until a
847 m_temporal
->set_always_current (name
);
850 // Set the global range of NAME to R.
853 ranger_cache::set_global_range (tree name
, const irange
&r
)
855 if (m_globals
.set_global_range (name
, r
))
857 // If there was already a range set, propagate the new value.
858 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
860 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
862 if (DEBUG_RANGE_CACHE
)
863 fprintf (dump_file
, " GLOBAL :");
865 propagate_updated_value (name
, bb
);
867 // Constants no longer need to tracked. Any further refinement has to be
868 // undefined. Propagation works better with constants. PR 100512.
869 // Pointers which resolve to non-zero also do not need
870 // tracking in the cache as they will never change. See PR 98866.
871 // Timestamp must always be updated, or dependent calculations may
872 // not include this latest value. PR 100774.
875 || (POINTER_TYPE_P (TREE_TYPE (name
)) && r
.nonzero_p ()))
876 m_gori
.set_range_invariant (name
);
877 m_temporal
->set_timestamp (name
);
880 // Provide lookup for the gori-computes class to access the best known range
881 // of an ssa_name in any given basic block. Note, this does no additonal
882 // lookups, just accesses the data that is already known.
884 // Get the range of NAME when the def occurs in block BB. If BB is NULL
885 // get the best global value available.
888 ranger_cache::range_of_def (irange
&r
, tree name
, basic_block bb
)
890 gcc_checking_assert (gimple_range_ssa_p (name
));
891 gcc_checking_assert (!bb
|| bb
== gimple_bb (SSA_NAME_DEF_STMT (name
)));
893 // Pick up the best global range available.
894 if (!m_globals
.get_global_range (r
, name
))
896 // If that fails, try to calculate the range using just global values.
897 gimple
*s
= SSA_NAME_DEF_STMT (name
);
898 if (gimple_get_lhs (s
) == name
)
899 fold_range (r
, s
, get_global_range_query ());
901 r
= gimple_range_global (name
);
905 m_non_null
.adjust_range (r
, name
, bb
, false);
908 // Get the range of NAME as it occurs on entry to block BB.
911 ranger_cache::entry_range (irange
&r
, tree name
, basic_block bb
)
913 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
915 r
= gimple_range_global (name
);
919 // Look for the on-entry value of name in BB from the cache.
920 // Otherwise pick up the best available global value.
921 if (!m_on_entry
.get_bb_range (r
, name
, bb
))
922 range_of_def (r
, name
);
924 m_non_null
.adjust_range (r
, name
, bb
, false);
927 // Get the range of NAME as it occurs on exit from block BB.
930 ranger_cache::exit_range (irange
&r
, tree name
, basic_block bb
)
932 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
934 r
= gimple_range_global (name
);
938 gimple
*s
= SSA_NAME_DEF_STMT (name
);
939 basic_block def_bb
= gimple_bb (s
);
941 range_of_def (r
, name
, bb
);
943 entry_range (r
, name
, bb
);
947 // Implement range_of_expr.
950 ranger_cache::range_of_expr (irange
&r
, tree name
, gimple
*stmt
)
952 if (!gimple_range_ssa_p (name
))
954 get_tree_range (r
, name
, stmt
);
958 basic_block bb
= gimple_bb (stmt
);
959 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
960 basic_block def_bb
= gimple_bb (def_stmt
);
963 range_of_def (r
, name
, bb
);
965 entry_range (r
, name
, bb
);
970 // Implement range_on_edge. Always return the best available range.
973 ranger_cache::range_on_edge (irange
&r
, edge e
, tree expr
)
975 if (gimple_range_ssa_p (expr
))
977 exit_range (r
, expr
, e
->src
);
978 int_range_max edge_range
;
979 if (m_gori
.outgoing_edge_range_p (edge_range
, e
, expr
, *this))
980 r
.intersect (edge_range
);
984 return get_tree_range (r
, expr
, NULL
);
988 // Return a static range for NAME on entry to basic block BB in R. If
989 // calc is true, fill any cache entries required between BB and the
990 // def block for NAME. Otherwise, return false if the cache is empty.
993 ranger_cache::block_range (irange
&r
, basic_block bb
, tree name
, bool calc
)
995 gcc_checking_assert (gimple_range_ssa_p (name
));
997 // If there are no range calculations anywhere in the IL, global range
998 // applies everywhere, so don't bother caching it.
999 if (!m_gori
.has_edge_range_p (name
))
1004 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1005 basic_block def_bb
= NULL
;
1007 def_bb
= gimple_bb (def_stmt
);;
1010 // If we get to the entry block, this better be a default def
1011 // or range_on_entry was called for a block not dominated by
1013 gcc_checking_assert (SSA_NAME_IS_DEFAULT_DEF (name
));
1014 def_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1017 // There is no range on entry for the definition block.
1021 // Otherwise, go figure out what is known in predecessor blocks.
1022 fill_block_cache (name
, bb
, def_bb
);
1023 gcc_checking_assert (m_on_entry
.bb_range_p (name
, bb
));
1025 return m_on_entry
.get_bb_range (r
, name
, bb
);
1028 // Add BB to the list of blocks to update, unless it's already in the list.
1031 ranger_cache::add_to_update (basic_block bb
)
1033 // If propagation has failed for BB, or its already in the list, don't
1035 if (!bitmap_bit_p (m_propfail
, bb
->index
) && !m_update_list
.contains (bb
))
1036 m_update_list
.quick_push (bb
);
1039 // If there is anything in the propagation update_list, continue
1040 // processing NAME until the list of blocks is empty.
1043 ranger_cache::propagate_cache (tree name
)
1048 int_range_max new_range
;
1049 int_range_max current_range
;
1050 int_range_max e_range
;
1052 gcc_checking_assert (bitmap_empty_p (m_propfail
));
1053 // Process each block by seeing if its calculated range on entry is
1054 // the same as its cached value. If there is a difference, update
1055 // the cache to reflect the new value, and check to see if any
1056 // successors have cache entries which may need to be checked for
1059 while (m_update_list
.length () > 0)
1061 bb
= m_update_list
.pop ();
1062 gcc_checking_assert (m_on_entry
.bb_range_p (name
, bb
));
1063 m_on_entry
.get_bb_range (current_range
, name
, bb
);
1065 if (DEBUG_RANGE_CACHE
)
1067 fprintf (dump_file
, "FWD visiting block %d for ", bb
->index
);
1068 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1069 fprintf (dump_file
, " starting range : ");
1070 current_range
.dump (dump_file
);
1071 fprintf (dump_file
, "\n");
1074 // Calculate the "new" range on entry by unioning the pred edges.
1075 new_range
.set_undefined ();
1076 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1078 range_on_edge (e_range
, e
, name
);
1079 if (DEBUG_RANGE_CACHE
)
1081 fprintf (dump_file
, " edge %d->%d :", e
->src
->index
, bb
->index
);
1082 e_range
.dump (dump_file
);
1083 fprintf (dump_file
, "\n");
1085 new_range
.union_ (e_range
);
1086 if (new_range
.varying_p ())
1090 // If the range on entry has changed, update it.
1091 if (new_range
!= current_range
)
1093 bool ok_p
= m_on_entry
.set_bb_range (name
, bb
, new_range
);
1094 // If the cache couldn't set the value, mark it as failed.
1096 bitmap_set_bit (m_propfail
, bb
->index
);
1097 if (DEBUG_RANGE_CACHE
)
1101 fprintf (dump_file
, " Cache failure to store value:");
1102 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1103 fprintf (dump_file
, " ");
1107 fprintf (dump_file
, " Updating range to ");
1108 new_range
.dump (dump_file
);
1110 fprintf (dump_file
, "\n Updating blocks :");
1112 // Mark each successor that has a range to re-check its range
1113 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1114 if (m_on_entry
.bb_range_p (name
, e
->dest
))
1116 if (DEBUG_RANGE_CACHE
)
1117 fprintf (dump_file
, " bb%d",e
->dest
->index
);
1118 add_to_update (e
->dest
);
1120 if (DEBUG_RANGE_CACHE
)
1121 fprintf (dump_file
, "\n");
1124 if (DEBUG_RANGE_CACHE
)
1126 fprintf (dump_file
, "DONE visiting blocks for ");
1127 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1128 fprintf (dump_file
, "\n");
1130 bitmap_clear (m_propfail
);
1133 // Check to see if an update to the value for NAME in BB has any effect
1134 // on values already in the on-entry cache for successor blocks.
1135 // If it does, update them. Don't visit any blocks which dont have a cache
1139 ranger_cache::propagate_updated_value (tree name
, basic_block bb
)
1144 // The update work list should be empty at this point.
1145 gcc_checking_assert (m_update_list
.length () == 0);
1146 gcc_checking_assert (bb
);
1148 if (DEBUG_RANGE_CACHE
)
1150 fprintf (dump_file
, " UPDATE cache for ");
1151 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1152 fprintf (dump_file
, " in BB %d : successors : ", bb
->index
);
1154 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1156 // Only update active cache entries.
1157 if (m_on_entry
.bb_range_p (name
, e
->dest
))
1159 add_to_update (e
->dest
);
1160 if (DEBUG_RANGE_CACHE
)
1161 fprintf (dump_file
, " UPDATE: bb%d", e
->dest
->index
);
1164 if (m_update_list
.length () != 0)
1166 if (DEBUG_RANGE_CACHE
)
1167 fprintf (dump_file
, "\n");
1168 propagate_cache (name
);
1172 if (DEBUG_RANGE_CACHE
)
1173 fprintf (dump_file
, " : No updates!\n");
1177 // Make sure that the range-on-entry cache for NAME is set for block BB.
1178 // Work back through the CFG to DEF_BB ensuring the range is calculated
1179 // on the block/edges leading back to that point.
1182 ranger_cache::fill_block_cache (tree name
, basic_block bb
, basic_block def_bb
)
1186 int_range_max block_result
;
1187 int_range_max undefined
;
1189 // At this point we shouldn't be looking at the def, entry or exit block.
1190 gcc_checking_assert (bb
!= def_bb
&& bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) &&
1191 bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1193 // If the block cache is set, then we've already visited this block.
1194 if (m_on_entry
.bb_range_p (name
, bb
))
1197 // Visit each block back to the DEF. Initialize each one to UNDEFINED.
1198 // m_visited at the end will contain all the blocks that we needed to set
1199 // the range_on_entry cache for.
1200 m_workback
.truncate (0);
1201 m_workback
.quick_push (bb
);
1202 undefined
.set_undefined ();
1203 m_on_entry
.set_bb_range (name
, bb
, undefined
);
1204 gcc_checking_assert (m_update_list
.length () == 0);
1206 if (DEBUG_RANGE_CACHE
)
1208 fprintf (dump_file
, "\n");
1209 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1210 fprintf (dump_file
, " : ");
1213 while (m_workback
.length () > 0)
1215 basic_block node
= m_workback
.pop ();
1216 if (DEBUG_RANGE_CACHE
)
1218 fprintf (dump_file
, "BACK visiting block %d for ", node
->index
);
1219 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1220 fprintf (dump_file
, "\n");
1223 FOR_EACH_EDGE (e
, ei
, node
->preds
)
1225 basic_block pred
= e
->src
;
1228 if (DEBUG_RANGE_CACHE
)
1229 fprintf (dump_file
, " %d->%d ",e
->src
->index
, e
->dest
->index
);
1231 // If the pred block is the def block add this BB to update list.
1234 add_to_update (node
);
1238 // If the pred is entry but NOT def, then it is used before
1239 // defined, it'll get set to [] and no need to update it.
1240 if (pred
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1242 if (DEBUG_RANGE_CACHE
)
1243 fprintf (dump_file
, "entry: bail.");
1247 // Regardless of whether we have visited pred or not, if the
1248 // pred has a non-null reference, revisit this block.
1249 // Don't search the DOM tree.
1250 if (m_non_null
.non_null_deref_p (name
, pred
, false))
1252 if (DEBUG_RANGE_CACHE
)
1253 fprintf (dump_file
, "nonnull: update ");
1254 add_to_update (node
);
1257 // If the pred block already has a range, or if it can contribute
1258 // something new. Ie, the edge generates a range of some sort.
1259 if (m_on_entry
.get_bb_range (r
, name
, pred
))
1261 if (DEBUG_RANGE_CACHE
)
1263 fprintf (dump_file
, "has cache, ");
1265 fprintf (dump_file
, ", ");
1267 if (!r
.undefined_p () || m_gori
.has_edge_range_p (name
, e
))
1269 add_to_update (node
);
1270 if (DEBUG_RANGE_CACHE
)
1271 fprintf (dump_file
, "update. ");
1276 if (DEBUG_RANGE_CACHE
)
1277 fprintf (dump_file
, "pushing undefined pred block.\n");
1278 // If the pred hasn't been visited (has no range), add it to
1280 gcc_checking_assert (!m_on_entry
.bb_range_p (name
, pred
));
1281 m_on_entry
.set_bb_range (name
, pred
, undefined
);
1282 m_workback
.quick_push (pred
);
1286 if (DEBUG_RANGE_CACHE
)
1287 fprintf (dump_file
, "\n");
1289 // Now fill in the marked blocks with values.
1290 propagate_cache (name
);
1291 if (DEBUG_RANGE_CACHE
)
1292 fprintf (dump_file
, " Propagation update done.\n");