1 /* Gimple ranger SSA cache implementation.
2 Copyright (C) 2017-2023 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"
31 #include "value-range-storage.h"
35 #include "gimple-iterator.h"
36 #include "gimple-walk.h"
39 #define DEBUG_RANGE_CACHE (dump_file \
40 && (param_ranger_debug & RANGER_DEBUG_CACHE))
42 // This class represents the API into a cache of ranges for an SSA_NAME.
43 // Routines must be implemented to set, get, and query if a value is set.
45 class ssa_block_ranges
48 ssa_block_ranges (tree t
) : m_type (t
) { }
49 virtual bool set_bb_range (const_basic_block bb
, const vrange
&r
) = 0;
50 virtual bool get_bb_range (vrange
&r
, const_basic_block bb
) = 0;
51 virtual bool bb_range_p (const_basic_block bb
) = 0;
58 // Print the list of known ranges for file F in a nice format.
61 ssa_block_ranges::dump (FILE *f
)
64 Value_Range
r (m_type
);
66 FOR_EACH_BB_FN (bb
, cfun
)
67 if (get_bb_range (r
, bb
))
69 fprintf (f
, "BB%d -> ", bb
->index
);
75 // This class implements the range cache as a linear vector, indexed by BB.
76 // It caches a varying and undefined range which are used instead of
77 // allocating new ones each time.
79 class sbr_vector
: public ssa_block_ranges
82 sbr_vector (tree t
, vrange_allocator
*allocator
, bool zero_p
= true);
84 virtual bool set_bb_range (const_basic_block bb
, const vrange
&r
) override
;
85 virtual bool get_bb_range (vrange
&r
, const_basic_block bb
) override
;
86 virtual bool bb_range_p (const_basic_block bb
) override
;
88 vrange_storage
**m_tab
; // Non growing vector.
90 vrange_storage
*m_varying
;
91 vrange_storage
*m_undefined
;
93 vrange_allocator
*m_range_allocator
;
99 // Initialize a block cache for an ssa_name of type T.
101 sbr_vector::sbr_vector (tree t
, vrange_allocator
*allocator
, bool zero_p
)
102 : ssa_block_ranges (t
)
104 gcc_checking_assert (TYPE_P (t
));
107 m_range_allocator
= allocator
;
108 m_tab_size
= last_basic_block_for_fn (cfun
) + 1;
109 m_tab
= static_cast <vrange_storage
**>
110 (allocator
->alloc (m_tab_size
* sizeof (vrange_storage
*)));
112 memset (m_tab
, 0, m_tab_size
* sizeof (vrange
*));
114 // Create the cached type range.
115 m_varying
= m_range_allocator
->clone_varying (t
);
116 m_undefined
= m_range_allocator
->clone_undefined (t
);
119 // Grow the vector when the CFG has increased in size.
124 int curr_bb_size
= last_basic_block_for_fn (cfun
);
125 gcc_checking_assert (curr_bb_size
> m_tab_size
);
127 // Increase the max of a)128, b)needed increase * 2, c)10% of current_size.
128 int inc
= MAX ((curr_bb_size
- m_tab_size
) * 2, 128);
129 inc
= MAX (inc
, curr_bb_size
/ 10);
130 int new_size
= inc
+ curr_bb_size
;
132 // Allocate new memory, copy the old vector and clear the new space.
133 vrange_storage
**t
= static_cast <vrange_storage
**>
134 (m_range_allocator
->alloc (new_size
* sizeof (vrange_storage
*)));
135 memcpy (t
, m_tab
, m_tab_size
* sizeof (vrange_storage
*));
137 memset (t
+ m_tab_size
, 0, (new_size
- m_tab_size
) * sizeof (vrange_storage
*));
140 m_tab_size
= new_size
;
143 // Set the range for block BB to be R.
146 sbr_vector::set_bb_range (const_basic_block bb
, const vrange
&r
)
149 if (bb
->index
>= m_tab_size
)
153 else if (r
.undefined_p ())
156 m
= m_range_allocator
->clone (r
);
157 m_tab
[bb
->index
] = m
;
161 // Return the range associated with block BB in R. Return false if
162 // there is no range.
165 sbr_vector::get_bb_range (vrange
&r
, const_basic_block bb
)
167 if (bb
->index
>= m_tab_size
)
169 vrange_storage
*m
= m_tab
[bb
->index
];
172 m
->get_vrange (r
, m_type
);
178 // Return true if a range is present.
181 sbr_vector::bb_range_p (const_basic_block bb
)
183 if (bb
->index
< m_tab_size
)
184 return m_tab
[bb
->index
] != NULL
;
188 // Like an sbr_vector, except it uses a bitmap to manage whetehr vale is set
189 // or not rather than cleared memory.
191 class sbr_lazy_vector
: public sbr_vector
194 sbr_lazy_vector (tree t
, vrange_allocator
*allocator
, bitmap_obstack
*bm
);
196 virtual bool set_bb_range (const_basic_block bb
, const vrange
&r
) override
;
197 virtual bool get_bb_range (vrange
&r
, const_basic_block bb
) override
;
198 virtual bool bb_range_p (const_basic_block bb
) override
;
203 sbr_lazy_vector::sbr_lazy_vector (tree t
, vrange_allocator
*allocator
,
205 : sbr_vector (t
, allocator
, false)
207 m_has_value
= BITMAP_ALLOC (bm
);
211 sbr_lazy_vector::set_bb_range (const_basic_block bb
, const vrange
&r
)
213 sbr_vector::set_bb_range (bb
, r
);
214 bitmap_set_bit (m_has_value
, bb
->index
);
219 sbr_lazy_vector::get_bb_range (vrange
&r
, const_basic_block bb
)
221 if (bitmap_bit_p (m_has_value
, bb
->index
))
222 return sbr_vector::get_bb_range (r
, bb
);
227 sbr_lazy_vector::bb_range_p (const_basic_block bb
)
229 return bitmap_bit_p (m_has_value
, bb
->index
);
232 // This class implements the on entry cache via a sparse bitmap.
233 // It uses the quad bit routines to access 4 bits at a time.
234 // A value of 0 (the default) means there is no entry, and a value of
235 // 1 thru SBR_NUM represents an element in the m_range vector.
236 // Varying is given the first value (1) and pre-cached.
237 // SBR_NUM + 1 represents the value of UNDEFINED, and is never stored.
238 // SBR_NUM is the number of values that can be cached.
239 // Indexes are 1..SBR_NUM and are stored locally at m_range[0..SBR_NUM-1]
242 #define SBR_UNDEF SBR_NUM + 1
243 #define SBR_VARYING 1
245 class sbr_sparse_bitmap
: public ssa_block_ranges
248 sbr_sparse_bitmap (tree t
, vrange_allocator
*allocator
, bitmap_obstack
*bm
);
249 virtual bool set_bb_range (const_basic_block bb
, const vrange
&r
) override
;
250 virtual bool get_bb_range (vrange
&r
, const_basic_block bb
) override
;
251 virtual bool bb_range_p (const_basic_block bb
) override
;
253 void bitmap_set_quad (bitmap head
, int quad
, int quad_value
);
254 int bitmap_get_quad (const_bitmap head
, int quad
);
255 vrange_allocator
*m_range_allocator
;
256 vrange_storage
*m_range
[SBR_NUM
];
261 // Initialize a block cache for an ssa_name of type T.
263 sbr_sparse_bitmap::sbr_sparse_bitmap (tree t
, vrange_allocator
*allocator
,
265 : ssa_block_ranges (t
)
267 gcc_checking_assert (TYPE_P (t
));
269 bitmap_initialize (&bitvec
, bm
);
270 bitmap_tree_view (&bitvec
);
271 m_range_allocator
= allocator
;
272 // Pre-cache varying.
273 m_range
[0] = m_range_allocator
->clone_varying (t
);
274 // Pre-cache zero and non-zero values for pointers.
275 if (POINTER_TYPE_P (t
))
277 int_range
<2> nonzero
;
278 nonzero
.set_nonzero (t
);
279 m_range
[1] = m_range_allocator
->clone (nonzero
);
282 m_range
[2] = m_range_allocator
->clone (zero
);
285 m_range
[1] = m_range
[2] = NULL
;
286 // Clear SBR_NUM entries.
287 for (int x
= 3; x
< SBR_NUM
; x
++)
291 // Set 4 bit values in a sparse bitmap. This allows a bitmap to
292 // function as a sparse array of 4 bit values.
293 // QUAD is the index, QUAD_VALUE is the 4 bit value to set.
296 sbr_sparse_bitmap::bitmap_set_quad (bitmap head
, int quad
, int quad_value
)
298 bitmap_set_aligned_chunk (head
, quad
, 4, (BITMAP_WORD
) quad_value
);
301 // Get a 4 bit value from a sparse bitmap. This allows a bitmap to
302 // function as a sparse array of 4 bit values.
303 // QUAD is the index.
305 sbr_sparse_bitmap::bitmap_get_quad (const_bitmap head
, int quad
)
307 return (int) bitmap_get_aligned_chunk (head
, quad
, 4);
310 // Set the range on entry to basic block BB to R.
313 sbr_sparse_bitmap::set_bb_range (const_basic_block bb
, const vrange
&r
)
315 if (r
.undefined_p ())
317 bitmap_set_quad (&bitvec
, bb
->index
, SBR_UNDEF
);
321 // Loop thru the values to see if R is already present.
322 for (int x
= 0; x
< SBR_NUM
; x
++)
323 if (!m_range
[x
] || m_range
[x
]->equal_p (r
))
326 m_range
[x
] = m_range_allocator
->clone (r
);
327 bitmap_set_quad (&bitvec
, bb
->index
, x
+ 1);
330 // All values are taken, default to VARYING.
331 bitmap_set_quad (&bitvec
, bb
->index
, SBR_VARYING
);
335 // Return the range associated with block BB in R. Return false if
336 // there is no range.
339 sbr_sparse_bitmap::get_bb_range (vrange
&r
, const_basic_block bb
)
341 int value
= bitmap_get_quad (&bitvec
, bb
->index
);
346 gcc_checking_assert (value
<= SBR_UNDEF
);
347 if (value
== SBR_UNDEF
)
350 m_range
[value
- 1]->get_vrange (r
, m_type
);
354 // Return true if a range is present.
357 sbr_sparse_bitmap::bb_range_p (const_basic_block bb
)
359 return (bitmap_get_quad (&bitvec
, bb
->index
) != 0);
362 // -------------------------------------------------------------------------
364 // Initialize the block cache.
366 block_range_cache::block_range_cache ()
368 bitmap_obstack_initialize (&m_bitmaps
);
369 m_ssa_ranges
.create (0);
370 m_ssa_ranges
.safe_grow_cleared (num_ssa_names
);
371 m_range_allocator
= new vrange_allocator
;
374 // Remove any m_block_caches which have been created.
376 block_range_cache::~block_range_cache ()
378 delete m_range_allocator
;
379 // Release the vector itself.
380 m_ssa_ranges
.release ();
381 bitmap_obstack_release (&m_bitmaps
);
384 // Set the range for NAME on entry to block BB to R.
385 // If it has not been accessed yet, allocate it first.
388 block_range_cache::set_bb_range (tree name
, const_basic_block bb
,
391 unsigned v
= SSA_NAME_VERSION (name
);
392 if (v
>= m_ssa_ranges
.length ())
393 m_ssa_ranges
.safe_grow_cleared (num_ssa_names
+ 1);
395 if (!m_ssa_ranges
[v
])
397 // Use sparse bitmap representation if there are too many basic blocks.
398 if (last_basic_block_for_fn (cfun
) > param_vrp_sparse_threshold
)
400 void *r
= m_range_allocator
->alloc (sizeof (sbr_sparse_bitmap
));
401 m_ssa_ranges
[v
] = new (r
) sbr_sparse_bitmap (TREE_TYPE (name
),
405 else if (last_basic_block_for_fn (cfun
) < param_vrp_vector_threshold
)
407 // For small CFGs use the basic vector implemntation.
408 void *r
= m_range_allocator
->alloc (sizeof (sbr_vector
));
409 m_ssa_ranges
[v
] = new (r
) sbr_vector (TREE_TYPE (name
),
414 // Otherwise use the sparse vector implementation.
415 void *r
= m_range_allocator
->alloc (sizeof (sbr_lazy_vector
));
416 m_ssa_ranges
[v
] = new (r
) sbr_lazy_vector (TREE_TYPE (name
),
421 return m_ssa_ranges
[v
]->set_bb_range (bb
, r
);
425 // Return a pointer to the ssa_block_cache for NAME. If it has not been
426 // accessed yet, return NULL.
428 inline ssa_block_ranges
*
429 block_range_cache::query_block_ranges (tree name
)
431 unsigned v
= SSA_NAME_VERSION (name
);
432 if (v
>= m_ssa_ranges
.length () || !m_ssa_ranges
[v
])
434 return m_ssa_ranges
[v
];
439 // Return the range for NAME on entry to BB in R. Return true if there
443 block_range_cache::get_bb_range (vrange
&r
, tree name
, const_basic_block bb
)
445 ssa_block_ranges
*ptr
= query_block_ranges (name
);
447 return ptr
->get_bb_range (r
, bb
);
451 // Return true if NAME has a range set in block BB.
454 block_range_cache::bb_range_p (tree name
, const_basic_block bb
)
456 ssa_block_ranges
*ptr
= query_block_ranges (name
);
458 return ptr
->bb_range_p (bb
);
462 // Print all known block caches to file F.
465 block_range_cache::dump (FILE *f
)
468 for (x
= 0; x
< m_ssa_ranges
.length (); ++x
)
472 fprintf (f
, " Ranges for ");
473 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
475 m_ssa_ranges
[x
]->dump (f
);
481 // Print all known ranges on entry to block BB to file F.
484 block_range_cache::dump (FILE *f
, basic_block bb
, bool print_varying
)
487 bool summarize_varying
= false;
488 for (x
= 1; x
< m_ssa_ranges
.length (); ++x
)
490 if (!gimple_range_ssa_p (ssa_name (x
)))
493 Value_Range
r (TREE_TYPE (ssa_name (x
)));
494 if (m_ssa_ranges
[x
] && m_ssa_ranges
[x
]->get_bb_range (r
, bb
))
496 if (!print_varying
&& r
.varying_p ())
498 summarize_varying
= true;
501 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
507 // If there were any varying entries, lump them all together.
508 if (summarize_varying
)
510 fprintf (f
, "VARYING_P on entry : ");
511 for (x
= 1; x
< num_ssa_names
; ++x
)
513 if (!gimple_range_ssa_p (ssa_name (x
)))
516 Value_Range
r (TREE_TYPE (ssa_name (x
)));
517 if (m_ssa_ranges
[x
] && m_ssa_ranges
[x
]->get_bb_range (r
, bb
))
521 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
530 // -------------------------------------------------------------------------
532 // Initialize an ssa cache.
534 ssa_cache::ssa_cache ()
537 m_range_allocator
= new vrange_allocator
;
540 // Deconstruct an ssa cache.
542 ssa_cache::~ssa_cache ()
545 delete m_range_allocator
;
548 // Enable a query to evaluate staements/ramnges based on picking up ranges
549 // from just an ssa-cache.
552 ssa_cache::range_of_expr (vrange
&r
, tree expr
, gimple
*stmt
)
554 if (!gimple_range_ssa_p (expr
))
555 return get_tree_range (r
, expr
, stmt
);
557 if (!get_range (r
, expr
))
558 gimple_range_global (r
, expr
, cfun
);
562 // Return TRUE if the global range of NAME has a cache entry.
565 ssa_cache::has_range (tree name
) const
567 unsigned v
= SSA_NAME_VERSION (name
);
568 if (v
>= m_tab
.length ())
570 return m_tab
[v
] != NULL
;
573 // Retrieve the global range of NAME from cache memory if it exists.
574 // Return the value in R.
577 ssa_cache::get_range (vrange
&r
, tree name
) const
579 unsigned v
= SSA_NAME_VERSION (name
);
580 if (v
>= m_tab
.length ())
583 vrange_storage
*stow
= m_tab
[v
];
586 stow
->get_vrange (r
, TREE_TYPE (name
));
590 // Set the range for NAME to R in the ssa cache.
591 // Return TRUE if there was already a range set, otherwise false.
594 ssa_cache::set_range (tree name
, const vrange
&r
)
596 unsigned v
= SSA_NAME_VERSION (name
);
597 if (v
>= m_tab
.length ())
598 m_tab
.safe_grow_cleared (num_ssa_names
+ 1);
600 vrange_storage
*m
= m_tab
[v
];
601 if (m
&& m
->fits_p (r
))
604 m_tab
[v
] = m_range_allocator
->clone (r
);
608 // Set the range for NAME to R in the ssa cache.
611 ssa_cache::clear_range (tree name
)
613 unsigned v
= SSA_NAME_VERSION (name
);
614 if (v
>= m_tab
.length ())
619 // Clear the ssa cache.
624 if (m_tab
.address ())
625 memset (m_tab
.address(), 0, m_tab
.length () * sizeof (vrange
*));
628 // Dump the contents of the ssa cache to F.
631 ssa_cache::dump (FILE *f
)
633 /* Cleared after the table header has been printed. */
634 bool print_header
= true;
635 for (unsigned x
= 1; x
< num_ssa_names
; x
++)
637 if (!gimple_range_ssa_p (ssa_name (x
)))
639 Value_Range
r (TREE_TYPE (ssa_name (x
)));
640 // Invoke dump_range_query which is a private virtual version of
641 // get_range. This avoids performance impacts on general queries,
642 // but allows sharing of the dump routine.
643 if (get_range (r
, ssa_name (x
)) && !r
.varying_p ())
647 /* Print the header only when there's something else
649 fprintf (f
, "Non-varying global ranges:\n");
650 fprintf (f
, "=========================:\n");
651 print_header
= false;
654 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
665 // Return true if NAME has an active range in the cache.
668 ssa_lazy_cache::has_range (tree name
) const
670 return bitmap_bit_p (active_p
, SSA_NAME_VERSION (name
));
673 // Set range of NAME to R in a lazy cache. Return FALSE if it did not already
677 ssa_lazy_cache::set_range (tree name
, const vrange
&r
)
679 unsigned v
= SSA_NAME_VERSION (name
);
680 if (!bitmap_set_bit (active_p
, v
))
682 // There is already an entry, simply set it.
683 gcc_checking_assert (v
< m_tab
.length ());
684 return ssa_cache::set_range (name
, r
);
686 if (v
>= m_tab
.length ())
687 m_tab
.safe_grow (num_ssa_names
+ 1);
688 m_tab
[v
] = m_range_allocator
->clone (r
);
692 // Return TRUE if NAME has a range, and return it in R.
695 ssa_lazy_cache::get_range (vrange
&r
, tree name
) const
697 if (!bitmap_bit_p (active_p
, SSA_NAME_VERSION (name
)))
699 return ssa_cache::get_range (r
, name
);
702 // Remove NAME from the active range list.
705 ssa_lazy_cache::clear_range (tree name
)
707 bitmap_clear_bit (active_p
, SSA_NAME_VERSION (name
));
710 // Remove all ranges from the active range list.
713 ssa_lazy_cache::clear ()
715 bitmap_clear (active_p
);
718 // --------------------------------------------------------------------------
721 // This class will manage the timestamps for each ssa_name.
722 // When a value is calculated, the timestamp is set to the current time.
723 // Current time is then incremented. Any dependencies will already have
724 // been calculated, and will thus have older timestamps.
725 // If one of those values is ever calculated again, it will get a newer
726 // timestamp, and the "current_p" check will fail.
733 bool current_p (tree name
, tree dep1
, tree dep2
) const;
734 void set_timestamp (tree name
);
735 void set_always_current (tree name
, bool value
);
736 bool always_current_p (tree name
) const;
738 int temporal_value (unsigned ssa
) const;
740 vec
<int> m_timestamp
;
744 temporal_cache::temporal_cache ()
747 m_timestamp
.create (0);
748 m_timestamp
.safe_grow_cleared (num_ssa_names
);
752 temporal_cache::~temporal_cache ()
754 m_timestamp
.release ();
757 // Return the timestamp value for SSA, or 0 if there isn't one.
760 temporal_cache::temporal_value (unsigned ssa
) const
762 if (ssa
>= m_timestamp
.length ())
764 return abs (m_timestamp
[ssa
]);
767 // Return TRUE if the timestamp for NAME is newer than any of its dependents.
768 // Up to 2 dependencies can be checked.
771 temporal_cache::current_p (tree name
, tree dep1
, tree dep2
) const
773 if (always_current_p (name
))
776 // Any non-registered dependencies will have a value of 0 and thus be older.
777 // Return true if time is newer than either dependent.
778 int ts
= temporal_value (SSA_NAME_VERSION (name
));
779 if (dep1
&& ts
< temporal_value (SSA_NAME_VERSION (dep1
)))
781 if (dep2
&& ts
< temporal_value (SSA_NAME_VERSION (dep2
)))
787 // This increments the global timer and sets the timestamp for NAME.
790 temporal_cache::set_timestamp (tree name
)
792 unsigned v
= SSA_NAME_VERSION (name
);
793 if (v
>= m_timestamp
.length ())
794 m_timestamp
.safe_grow_cleared (num_ssa_names
+ 20);
795 m_timestamp
[v
] = ++m_current_time
;
798 // Set the timestamp to 0, marking it as "always up to date".
801 temporal_cache::set_always_current (tree name
, bool value
)
803 unsigned v
= SSA_NAME_VERSION (name
);
804 if (v
>= m_timestamp
.length ())
805 m_timestamp
.safe_grow_cleared (num_ssa_names
+ 20);
807 int ts
= abs (m_timestamp
[v
]);
808 // If this does not have a timestamp, create one.
810 ts
= ++m_current_time
;
811 m_timestamp
[v
] = value
? -ts
: ts
;
814 // Return true if NAME is always current.
817 temporal_cache::always_current_p (tree name
) const
819 unsigned v
= SSA_NAME_VERSION (name
);
820 if (v
>= m_timestamp
.length ())
822 return m_timestamp
[v
] <= 0;
825 // --------------------------------------------------------------------------
827 // This class provides an abstraction of a list of blocks to be updated
828 // by the cache. It is currently a stack but could be changed. It also
829 // maintains a list of blocks which have failed propagation, and does not
830 // enter any of those blocks into the list.
832 // A vector over the BBs is maintained, and an entry of 0 means it is not in
833 // a list. Otherwise, the entry is the next block in the list. -1 terminates
834 // the list. m_head points to the top of the list, -1 if the list is empty.
841 void add (basic_block bb
);
843 inline bool empty_p () { return m_update_head
== -1; }
844 inline void clear_failures () { bitmap_clear (m_propfail
); }
845 inline void propagation_failed (basic_block bb
)
846 { bitmap_set_bit (m_propfail
, bb
->index
); }
848 vec
<int> m_update_list
;
853 // Create an update list.
855 update_list::update_list ()
857 m_update_list
.create (0);
858 m_update_list
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 64);
860 m_propfail
= BITMAP_ALLOC (NULL
);
863 // Destroy an update list.
865 update_list::~update_list ()
867 m_update_list
.release ();
868 BITMAP_FREE (m_propfail
);
871 // Add BB to the list of blocks to update, unless it's already in the list.
874 update_list::add (basic_block bb
)
877 // If propagation has failed for BB, or its already in the list, don't
879 if ((unsigned)i
>= m_update_list
.length ())
880 m_update_list
.safe_grow_cleared (i
+ 64);
881 if (!m_update_list
[i
] && !bitmap_bit_p (m_propfail
, i
))
886 m_update_list
[i
] = -1;
890 gcc_checking_assert (m_update_head
> 0);
891 m_update_list
[i
] = m_update_head
;
897 // Remove a block from the list.
902 gcc_checking_assert (!empty_p ());
903 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, m_update_head
);
904 int pop
= m_update_head
;
905 m_update_head
= m_update_list
[pop
];
906 m_update_list
[pop
] = 0;
910 // --------------------------------------------------------------------------
912 ranger_cache::ranger_cache (int not_executable_flag
, bool use_imm_uses
)
913 : m_gori (not_executable_flag
),
914 m_exit (use_imm_uses
)
916 m_workback
.create (0);
917 m_workback
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
918 m_workback
.truncate (0);
919 m_temporal
= new temporal_cache
;
920 // If DOM info is available, spawn an oracle as well.
921 if (dom_info_available_p (CDI_DOMINATORS
))
922 m_oracle
= new dom_oracle ();
926 unsigned x
, lim
= last_basic_block_for_fn (cfun
);
927 // Calculate outgoing range info upfront. This will fully populate the
928 // m_maybe_variant bitmap which will help eliminate processing of names
929 // which never have their ranges adjusted.
930 for (x
= 0; x
< lim
; x
++)
932 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, x
);
936 m_update
= new update_list ();
939 ranger_cache::~ranger_cache ()
945 m_workback
.release ();
948 // Dump the global caches to file F. if GORI_DUMP is true, dump the
952 ranger_cache::dump (FILE *f
)
958 // Dump the caches for basic block BB to file F.
961 ranger_cache::dump_bb (FILE *f
, basic_block bb
)
963 m_gori
.gori_map::dump (f
, bb
, false);
964 m_on_entry
.dump (f
, bb
);
966 m_oracle
->dump (f
, bb
);
969 // Get the global range for NAME, and return in R. Return false if the
970 // global range is not set, and return the legacy global value in R.
973 ranger_cache::get_global_range (vrange
&r
, tree name
) const
975 if (m_globals
.get_range (r
, name
))
977 gimple_range_global (r
, name
);
981 // Get the global range for NAME, and return in R. Return false if the
982 // global range is not set, and R will contain the legacy global value.
983 // CURRENT_P is set to true if the value was in cache and not stale.
984 // Otherwise, set CURRENT_P to false and mark as it always current.
985 // If the global cache did not have a value, initialize it as well.
986 // After this call, the global cache will have a value.
989 ranger_cache::get_global_range (vrange
&r
, tree name
, bool ¤t_p
)
991 bool had_global
= get_global_range (r
, name
);
993 // If there was a global value, set current flag, otherwise set a value.
996 current_p
= r
.singleton_p ()
997 || m_temporal
->current_p (name
, m_gori
.depend1 (name
),
998 m_gori
.depend2 (name
));
1001 // If no global value has been set and value is VARYING, fold the stmt
1002 // using just global ranges to get a better initial value.
1003 // After inlining we tend to decide some things are constant, so
1004 // so not do this evaluation after inlining.
1005 if (r
.varying_p () && !cfun
->after_inlining
)
1007 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1008 if (gimple_get_lhs (s
) == name
)
1010 if (!fold_range (r
, s
, get_global_range_query ()))
1011 gimple_range_global (r
, name
);
1014 m_globals
.set_range (name
, r
);
1017 // If the existing value was not current, mark it as always current.
1019 m_temporal
->set_always_current (name
, true);
1023 // Set the global range of NAME to R and give it a timestamp.
1026 ranger_cache::set_global_range (tree name
, const vrange
&r
, bool changed
)
1028 // Setting a range always clears the always_current flag.
1029 m_temporal
->set_always_current (name
, false);
1032 // If there are dependencies, make sure this is not out of date.
1033 if (!m_temporal
->current_p (name
, m_gori
.depend1 (name
),
1034 m_gori
.depend2 (name
)))
1035 m_temporal
->set_timestamp (name
);
1038 if (m_globals
.set_range (name
, r
))
1040 // If there was already a range set, propagate the new value.
1041 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
1043 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1045 if (DEBUG_RANGE_CACHE
)
1046 fprintf (dump_file
, " GLOBAL :");
1048 propagate_updated_value (name
, bb
);
1050 // Constants no longer need to tracked. Any further refinement has to be
1051 // undefined. Propagation works better with constants. PR 100512.
1052 // Pointers which resolve to non-zero also do not need
1053 // tracking in the cache as they will never change. See PR 98866.
1054 // Timestamp must always be updated, or dependent calculations may
1055 // not include this latest value. PR 100774.
1057 if (r
.singleton_p ()
1058 || (POINTER_TYPE_P (TREE_TYPE (name
)) && r
.nonzero_p ()))
1059 m_gori
.set_range_invariant (name
);
1060 m_temporal
->set_timestamp (name
);
1063 // Provide lookup for the gori-computes class to access the best known range
1064 // of an ssa_name in any given basic block. Note, this does no additional
1065 // lookups, just accesses the data that is already known.
1067 // Get the range of NAME when the def occurs in block BB. If BB is NULL
1068 // get the best global value available.
1071 ranger_cache::range_of_def (vrange
&r
, tree name
, basic_block bb
)
1073 gcc_checking_assert (gimple_range_ssa_p (name
));
1074 gcc_checking_assert (!bb
|| bb
== gimple_bb (SSA_NAME_DEF_STMT (name
)));
1076 // Pick up the best global range available.
1077 if (!m_globals
.get_range (r
, name
))
1079 // If that fails, try to calculate the range using just global values.
1080 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1081 if (gimple_get_lhs (s
) == name
)
1082 fold_range (r
, s
, get_global_range_query ());
1084 gimple_range_global (r
, name
);
1088 // Get the range of NAME as it occurs on entry to block BB. Use MODE for
1092 ranger_cache::entry_range (vrange
&r
, tree name
, basic_block bb
,
1095 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1097 gimple_range_global (r
, name
);
1101 // Look for the on-entry value of name in BB from the cache.
1102 // Otherwise pick up the best available global value.
1103 if (!m_on_entry
.get_bb_range (r
, name
, bb
))
1104 if (!range_from_dom (r
, name
, bb
, mode
))
1105 range_of_def (r
, name
);
1108 // Get the range of NAME as it occurs on exit from block BB. Use MODE for
1112 ranger_cache::exit_range (vrange
&r
, tree name
, basic_block bb
,
1115 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1117 gimple_range_global (r
, name
);
1121 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1122 basic_block def_bb
= gimple_bb (s
);
1124 range_of_def (r
, name
, bb
);
1126 entry_range (r
, name
, bb
, mode
);
1129 // Get the range of NAME on edge E using MODE, return the result in R.
1130 // Always returns a range and true.
1133 ranger_cache::edge_range (vrange
&r
, edge e
, tree name
, enum rfd_mode mode
)
1135 exit_range (r
, name
, e
->src
, mode
);
1136 // If this is not an abnormal edge, check for inferred ranges on exit.
1137 if ((e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
)) == 0)
1138 m_exit
.maybe_adjust_range (r
, name
, e
->src
);
1139 Value_Range
er (TREE_TYPE (name
));
1140 if (m_gori
.outgoing_edge_range_p (er
, e
, name
, *this))
1147 // Implement range_of_expr.
1150 ranger_cache::range_of_expr (vrange
&r
, tree name
, gimple
*stmt
)
1152 if (!gimple_range_ssa_p (name
))
1154 get_tree_range (r
, name
, stmt
);
1158 basic_block bb
= gimple_bb (stmt
);
1159 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1160 basic_block def_bb
= gimple_bb (def_stmt
);
1163 range_of_def (r
, name
, bb
);
1165 entry_range (r
, name
, bb
, RFD_NONE
);
1170 // Implement range_on_edge. Always return the best available range using
1171 // the current cache values.
1174 ranger_cache::range_on_edge (vrange
&r
, edge e
, tree expr
)
1176 if (gimple_range_ssa_p (expr
))
1177 return edge_range (r
, e
, expr
, RFD_NONE
);
1178 return get_tree_range (r
, expr
, NULL
);
1181 // Return a static range for NAME on entry to basic block BB in R. If
1182 // calc is true, fill any cache entries required between BB and the
1183 // def block for NAME. Otherwise, return false if the cache is empty.
1186 ranger_cache::block_range (vrange
&r
, basic_block bb
, tree name
, bool calc
)
1188 gcc_checking_assert (gimple_range_ssa_p (name
));
1190 // If there are no range calculations anywhere in the IL, global range
1191 // applies everywhere, so don't bother caching it.
1192 if (!m_gori
.has_edge_range_p (name
))
1197 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1198 basic_block def_bb
= NULL
;
1200 def_bb
= gimple_bb (def_stmt
);;
1203 // If we get to the entry block, this better be a default def
1204 // or range_on_entry was called for a block not dominated by
1206 gcc_checking_assert (SSA_NAME_IS_DEFAULT_DEF (name
));
1207 def_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1210 // There is no range on entry for the definition block.
1214 // Otherwise, go figure out what is known in predecessor blocks.
1215 fill_block_cache (name
, bb
, def_bb
);
1216 gcc_checking_assert (m_on_entry
.bb_range_p (name
, bb
));
1218 return m_on_entry
.get_bb_range (r
, name
, bb
);
1221 // If there is anything in the propagation update_list, continue
1222 // processing NAME until the list of blocks is empty.
1225 ranger_cache::propagate_cache (tree name
)
1230 tree type
= TREE_TYPE (name
);
1231 Value_Range
new_range (type
);
1232 Value_Range
current_range (type
);
1233 Value_Range
e_range (type
);
1235 // Process each block by seeing if its calculated range on entry is
1236 // the same as its cached value. If there is a difference, update
1237 // the cache to reflect the new value, and check to see if any
1238 // successors have cache entries which may need to be checked for
1241 while (!m_update
->empty_p ())
1243 bb
= m_update
->pop ();
1244 gcc_checking_assert (m_on_entry
.bb_range_p (name
, bb
));
1245 m_on_entry
.get_bb_range (current_range
, name
, bb
);
1247 if (DEBUG_RANGE_CACHE
)
1249 fprintf (dump_file
, "FWD visiting block %d for ", bb
->index
);
1250 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1251 fprintf (dump_file
, " starting range : ");
1252 current_range
.dump (dump_file
);
1253 fprintf (dump_file
, "\n");
1256 // Calculate the "new" range on entry by unioning the pred edges.
1257 new_range
.set_undefined ();
1258 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1260 edge_range (e_range
, e
, name
, RFD_READ_ONLY
);
1261 if (DEBUG_RANGE_CACHE
)
1263 fprintf (dump_file
, " edge %d->%d :", e
->src
->index
, bb
->index
);
1264 e_range
.dump (dump_file
);
1265 fprintf (dump_file
, "\n");
1267 new_range
.union_ (e_range
);
1268 if (new_range
.varying_p ())
1272 // If the range on entry has changed, update it.
1273 if (new_range
!= current_range
)
1275 bool ok_p
= m_on_entry
.set_bb_range (name
, bb
, new_range
);
1276 // If the cache couldn't set the value, mark it as failed.
1278 m_update
->propagation_failed (bb
);
1279 if (DEBUG_RANGE_CACHE
)
1283 fprintf (dump_file
, " Cache failure to store value:");
1284 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1285 fprintf (dump_file
, " ");
1289 fprintf (dump_file
, " Updating range to ");
1290 new_range
.dump (dump_file
);
1292 fprintf (dump_file
, "\n Updating blocks :");
1294 // Mark each successor that has a range to re-check its range
1295 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1296 if (m_on_entry
.bb_range_p (name
, e
->dest
))
1298 if (DEBUG_RANGE_CACHE
)
1299 fprintf (dump_file
, " bb%d",e
->dest
->index
);
1300 m_update
->add (e
->dest
);
1302 if (DEBUG_RANGE_CACHE
)
1303 fprintf (dump_file
, "\n");
1306 if (DEBUG_RANGE_CACHE
)
1308 fprintf (dump_file
, "DONE visiting blocks for ");
1309 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1310 fprintf (dump_file
, "\n");
1312 m_update
->clear_failures ();
1315 // Check to see if an update to the value for NAME in BB has any effect
1316 // on values already in the on-entry cache for successor blocks.
1317 // If it does, update them. Don't visit any blocks which don't have a cache
1321 ranger_cache::propagate_updated_value (tree name
, basic_block bb
)
1326 // The update work list should be empty at this point.
1327 gcc_checking_assert (m_update
->empty_p ());
1328 gcc_checking_assert (bb
);
1330 if (DEBUG_RANGE_CACHE
)
1332 fprintf (dump_file
, " UPDATE cache for ");
1333 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1334 fprintf (dump_file
, " in BB %d : successors : ", bb
->index
);
1336 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1338 // Only update active cache entries.
1339 if (m_on_entry
.bb_range_p (name
, e
->dest
))
1341 m_update
->add (e
->dest
);
1342 if (DEBUG_RANGE_CACHE
)
1343 fprintf (dump_file
, " UPDATE: bb%d", e
->dest
->index
);
1346 if (!m_update
->empty_p ())
1348 if (DEBUG_RANGE_CACHE
)
1349 fprintf (dump_file
, "\n");
1350 propagate_cache (name
);
1354 if (DEBUG_RANGE_CACHE
)
1355 fprintf (dump_file
, " : No updates!\n");
1359 // Make sure that the range-on-entry cache for NAME is set for block BB.
1360 // Work back through the CFG to DEF_BB ensuring the range is calculated
1361 // on the block/edges leading back to that point.
1364 ranger_cache::fill_block_cache (tree name
, basic_block bb
, basic_block def_bb
)
1368 tree type
= TREE_TYPE (name
);
1369 Value_Range
block_result (type
);
1370 Value_Range
undefined (type
);
1372 // At this point we shouldn't be looking at the def, entry block.
1373 gcc_checking_assert (bb
!= def_bb
&& bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1374 gcc_checking_assert (m_workback
.length () == 0);
1376 // If the block cache is set, then we've already visited this block.
1377 if (m_on_entry
.bb_range_p (name
, bb
))
1380 if (DEBUG_RANGE_CACHE
)
1382 fprintf (dump_file
, "\n");
1383 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1384 fprintf (dump_file
, " : ");
1387 // Check if a dominators can supply the range.
1388 if (range_from_dom (block_result
, name
, bb
, RFD_FILL
))
1390 if (DEBUG_RANGE_CACHE
)
1392 fprintf (dump_file
, "Filled from dominator! : ");
1393 block_result
.dump (dump_file
);
1394 fprintf (dump_file
, "\n");
1396 // See if any equivalences can refine it.
1397 // PR 109462, like 108139 below, a one way equivalence introduced
1398 // by a PHI node can also be through the definition side. Disallow it.
1403 int prec
= TYPE_PRECISION (type
);
1404 FOR_EACH_PARTIAL_AND_FULL_EQUIV (m_oracle
, bb
, name
, equiv_name
, rel
)
1406 basic_block equiv_bb
= gimple_bb (SSA_NAME_DEF_STMT (equiv_name
));
1408 // Ignore partial equivs that are smaller than this object.
1409 if (rel
!= VREL_EQ
&& prec
> pe_to_bits (rel
))
1412 // Check if the equiv has any ranges calculated.
1413 if (!m_gori
.has_edge_range_p (equiv_name
))
1416 // Check if the equiv definition dominates this block
1417 if (equiv_bb
== bb
||
1418 (equiv_bb
&& !dominated_by_p (CDI_DOMINATORS
, bb
, equiv_bb
)))
1421 if (DEBUG_RANGE_CACHE
)
1424 fprintf (dump_file
, "Checking Equivalence (");
1426 fprintf (dump_file
, "Checking Partial equiv (");
1427 print_relation (dump_file
, rel
);
1428 fprintf (dump_file
, ") ");
1429 print_generic_expr (dump_file
, equiv_name
, TDF_SLIM
);
1430 fprintf (dump_file
, "\n");
1432 Value_Range
equiv_range (TREE_TYPE (equiv_name
));
1433 if (range_from_dom (equiv_range
, equiv_name
, bb
, RFD_READ_ONLY
))
1436 range_cast (equiv_range
, type
);
1437 if (block_result
.intersect (equiv_range
))
1439 if (DEBUG_RANGE_CACHE
)
1442 fprintf (dump_file
, "Equivalence update! : ");
1444 fprintf (dump_file
, "Partial equiv update! : ");
1445 print_generic_expr (dump_file
, equiv_name
, TDF_SLIM
);
1446 fprintf (dump_file
, " has range : ");
1447 equiv_range
.dump (dump_file
);
1448 fprintf (dump_file
, " refining range to :");
1449 block_result
.dump (dump_file
);
1450 fprintf (dump_file
, "\n");
1457 m_on_entry
.set_bb_range (name
, bb
, block_result
);
1458 gcc_checking_assert (m_workback
.length () == 0);
1462 // Visit each block back to the DEF. Initialize each one to UNDEFINED.
1463 // m_visited at the end will contain all the blocks that we needed to set
1464 // the range_on_entry cache for.
1465 m_workback
.quick_push (bb
);
1466 undefined
.set_undefined ();
1467 m_on_entry
.set_bb_range (name
, bb
, undefined
);
1468 gcc_checking_assert (m_update
->empty_p ());
1470 while (m_workback
.length () > 0)
1472 basic_block node
= m_workback
.pop ();
1473 if (DEBUG_RANGE_CACHE
)
1475 fprintf (dump_file
, "BACK visiting block %d for ", node
->index
);
1476 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1477 fprintf (dump_file
, "\n");
1480 FOR_EACH_EDGE (e
, ei
, node
->preds
)
1482 basic_block pred
= e
->src
;
1483 Value_Range
r (TREE_TYPE (name
));
1485 if (DEBUG_RANGE_CACHE
)
1486 fprintf (dump_file
, " %d->%d ",e
->src
->index
, e
->dest
->index
);
1488 // If the pred block is the def block add this BB to update list.
1491 m_update
->add (node
);
1495 // If the pred is entry but NOT def, then it is used before
1496 // defined, it'll get set to [] and no need to update it.
1497 if (pred
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1499 if (DEBUG_RANGE_CACHE
)
1500 fprintf (dump_file
, "entry: bail.");
1504 // Regardless of whether we have visited pred or not, if the
1505 // pred has inferred ranges, revisit this block.
1506 // Don't search the DOM tree.
1507 if (m_exit
.has_range_p (name
, pred
))
1509 if (DEBUG_RANGE_CACHE
)
1510 fprintf (dump_file
, "Inferred range: update ");
1511 m_update
->add (node
);
1514 // If the pred block already has a range, or if it can contribute
1515 // something new. Ie, the edge generates a range of some sort.
1516 if (m_on_entry
.get_bb_range (r
, name
, pred
))
1518 if (DEBUG_RANGE_CACHE
)
1520 fprintf (dump_file
, "has cache, ");
1522 fprintf (dump_file
, ", ");
1524 if (!r
.undefined_p () || m_gori
.has_edge_range_p (name
, e
))
1526 m_update
->add (node
);
1527 if (DEBUG_RANGE_CACHE
)
1528 fprintf (dump_file
, "update. ");
1533 if (DEBUG_RANGE_CACHE
)
1534 fprintf (dump_file
, "pushing undefined pred block.\n");
1535 // If the pred hasn't been visited (has no range), add it to
1537 gcc_checking_assert (!m_on_entry
.bb_range_p (name
, pred
));
1538 m_on_entry
.set_bb_range (name
, pred
, undefined
);
1539 m_workback
.quick_push (pred
);
1543 if (DEBUG_RANGE_CACHE
)
1544 fprintf (dump_file
, "\n");
1546 // Now fill in the marked blocks with values.
1547 propagate_cache (name
);
1548 if (DEBUG_RANGE_CACHE
)
1549 fprintf (dump_file
, " Propagation update done.\n");
1552 // Resolve the range of BB if the dominators range is R by calculating incoming
1553 // edges to this block. All lead back to the dominator so should be cheap.
1554 // The range for BB is set and returned in R.
1557 ranger_cache::resolve_dom (vrange
&r
, tree name
, basic_block bb
)
1559 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
1560 basic_block dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1562 // if it doesn't already have a value, store the incoming range.
1563 if (!m_on_entry
.bb_range_p (name
, dom_bb
) && def_bb
!= dom_bb
)
1565 // If the range can't be store, don't try to accumulate
1566 // the range in PREV_BB due to excessive recalculations.
1567 if (!m_on_entry
.set_bb_range (name
, dom_bb
, r
))
1570 // With the dominator set, we should be able to cheaply query
1571 // each incoming edge now and accumulate the results.
1575 Value_Range
er (TREE_TYPE (name
));
1576 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1578 // If the predecessor is dominated by this block, then there is a back
1579 // edge, and won't provide anything useful. We'll actually end up with
1580 // VARYING as we will not resolve this node.
1581 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
1583 edge_range (er
, e
, name
, RFD_READ_ONLY
);
1586 // Set the cache in PREV_BB so it is not calculated again.
1587 m_on_entry
.set_bb_range (name
, bb
, r
);
1590 // Get the range of NAME from dominators of BB and return it in R. Search the
1591 // dominator tree based on MODE.
1594 ranger_cache::range_from_dom (vrange
&r
, tree name
, basic_block start_bb
,
1597 if (mode
== RFD_NONE
|| !dom_info_available_p (CDI_DOMINATORS
))
1600 // Search back to the definition block or entry block.
1601 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
1603 def_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1606 basic_block prev_bb
= start_bb
;
1608 // Track any inferred ranges seen.
1609 Value_Range
infer (TREE_TYPE (name
));
1610 infer
.set_varying (TREE_TYPE (name
));
1612 // Range on entry to the DEF block should not be queried.
1613 gcc_checking_assert (start_bb
!= def_bb
);
1614 unsigned start_limit
= m_workback
.length ();
1616 // Default value is global range.
1617 get_global_range (r
, name
);
1619 // The dominator of EXIT_BLOCK doesn't seem to be set, so at least handle
1620 // the common single exit cases.
1621 if (start_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) && single_pred_p (start_bb
))
1622 bb
= single_pred_edge (start_bb
)->src
;
1624 bb
= get_immediate_dominator (CDI_DOMINATORS
, start_bb
);
1626 // Search until a value is found, pushing blocks which may need calculating.
1627 for ( ; bb
; prev_bb
= bb
, bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1629 // Accumulate any block exit inferred ranges.
1630 m_exit
.maybe_adjust_range (infer
, name
, bb
);
1632 // This block has an outgoing range.
1633 if (m_gori
.has_edge_range_p (name
, bb
))
1634 m_workback
.quick_push (prev_bb
);
1637 // Normally join blocks don't carry any new range information on
1638 // incoming edges. If the first incoming edge to this block does
1639 // generate a range, calculate the ranges if all incoming edges
1640 // are also dominated by the dominator. (Avoids backedges which
1641 // will break the rule of moving only upward in the dominator tree).
1642 // If the first pred does not generate a range, then we will be
1643 // using the dominator range anyway, so that's all the check needed.
1644 if (EDGE_COUNT (prev_bb
->preds
) > 1
1645 && m_gori
.has_edge_range_p (name
, EDGE_PRED (prev_bb
, 0)->src
))
1649 bool all_dom
= true;
1650 FOR_EACH_EDGE (e
, ei
, prev_bb
->preds
)
1652 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
1658 m_workback
.quick_push (prev_bb
);
1665 if (m_on_entry
.get_bb_range (r
, name
, bb
))
1669 if (DEBUG_RANGE_CACHE
)
1671 fprintf (dump_file
, "CACHE: BB %d DOM query for ", start_bb
->index
);
1672 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1673 fprintf (dump_file
, ", found ");
1676 fprintf (dump_file
, " at BB%d\n", bb
->index
);
1678 fprintf (dump_file
, " at function top\n");
1681 // Now process any blocks wit incoming edges that nay have adjustments.
1682 while (m_workback
.length () > start_limit
)
1684 Value_Range
er (TREE_TYPE (name
));
1685 prev_bb
= m_workback
.pop ();
1686 if (!single_pred_p (prev_bb
))
1688 // Non single pred means we need to cache a value in the dominator
1689 // so we can cheaply calculate incoming edges to this block, and
1690 // then store the resulting value. If processing mode is not
1691 // RFD_FILL, then the cache cant be stored to, so don't try.
1692 // Otherwise this becomes a quadratic timed calculation.
1693 if (mode
== RFD_FILL
)
1694 resolve_dom (r
, name
, prev_bb
);
1698 edge e
= single_pred_edge (prev_bb
);
1700 if (m_gori
.outgoing_edge_range_p (er
, e
, name
, *this))
1703 // If this is a normal edge, apply any inferred ranges.
1704 if ((e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
)) == 0)
1705 m_exit
.maybe_adjust_range (r
, name
, bb
);
1707 if (DEBUG_RANGE_CACHE
)
1709 fprintf (dump_file
, "CACHE: Adjusted edge range for %d->%d : ",
1710 bb
->index
, prev_bb
->index
);
1712 fprintf (dump_file
, "\n");
1717 // Apply non-null if appropriate.
1718 if (!has_abnormal_call_or_eh_pred_edge_p (start_bb
))
1719 r
.intersect (infer
);
1721 if (DEBUG_RANGE_CACHE
)
1723 fprintf (dump_file
, "CACHE: Range for DOM returns : ");
1725 fprintf (dump_file
, "\n");
1730 // This routine will register an inferred value in block BB, and possibly
1731 // update the on-entry cache if appropriate.
1734 ranger_cache::register_inferred_value (const vrange
&ir
, tree name
,
1737 Value_Range
r (TREE_TYPE (name
));
1738 if (!m_on_entry
.get_bb_range (r
, name
, bb
))
1739 exit_range (r
, name
, bb
, RFD_READ_ONLY
);
1740 if (r
.intersect (ir
))
1742 m_on_entry
.set_bb_range (name
, bb
, r
);
1743 // If this range was invariant before, remove invariant.
1744 if (!m_gori
.has_edge_range_p (name
))
1745 m_gori
.set_range_invariant (name
, false);
1749 // This routine is used during a block walk to adjust any inferred ranges
1750 // of operands on stmt S.
1753 ranger_cache::apply_inferred_ranges (gimple
*s
)
1757 basic_block bb
= gimple_bb (s
);
1758 gimple_infer_range
infer(s
);
1759 if (infer
.num () == 0)
1762 // Do not update the on-entry cache for block ending stmts.
1763 if (stmt_ends_bb_p (s
))
1767 FOR_EACH_EDGE (e
, ei
, gimple_bb (s
)->succs
)
1768 if (!(e
->flags
& (EDGE_ABNORMAL
|EDGE_EH
)))
1774 for (unsigned x
= 0; x
< infer
.num (); x
++)
1776 tree name
= infer
.name (x
);
1777 m_exit
.add_range (name
, bb
, infer
.range (x
));
1779 register_inferred_value (infer
.range (x
), name
, bb
);