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 // If NAME has a range, intersect it with R, otherwise set it to R.
609 // Return TRUE if the range is new or changes.
612 ssa_cache::merge_range (tree name
, const vrange
&r
)
614 unsigned v
= SSA_NAME_VERSION (name
);
615 if (v
>= m_tab
.length ())
616 m_tab
.safe_grow_cleared (num_ssa_names
+ 1);
618 vrange_storage
*m
= m_tab
[v
];
619 // Check if this is a new value.
621 m_tab
[v
] = m_range_allocator
->clone (r
);
624 Value_Range
curr (TREE_TYPE (name
));
625 m
->get_vrange (curr
, TREE_TYPE (name
));
626 // If there is no change, return false.
627 if (!curr
.intersect (r
))
630 if (m
->fits_p (curr
))
631 m
->set_vrange (curr
);
633 m_tab
[v
] = m_range_allocator
->clone (curr
);
638 // Set the range for NAME to R in the ssa cache.
641 ssa_cache::clear_range (tree name
)
643 unsigned v
= SSA_NAME_VERSION (name
);
644 if (v
>= m_tab
.length ())
649 // Clear the ssa cache.
654 if (m_tab
.address ())
655 memset (m_tab
.address(), 0, m_tab
.length () * sizeof (vrange
*));
658 // Dump the contents of the ssa cache to F.
661 ssa_cache::dump (FILE *f
)
663 for (unsigned x
= 1; x
< num_ssa_names
; x
++)
665 if (!gimple_range_ssa_p (ssa_name (x
)))
667 Value_Range
r (TREE_TYPE (ssa_name (x
)));
668 // Dump all non-varying ranges.
669 if (get_range (r
, ssa_name (x
)) && !r
.varying_p ())
671 print_generic_expr (f
, ssa_name (x
), TDF_NONE
);
680 // Return true if NAME has an active range in the cache.
683 ssa_lazy_cache::has_range (tree name
) const
685 return bitmap_bit_p (active_p
, SSA_NAME_VERSION (name
));
688 // Set range of NAME to R in a lazy cache. Return FALSE if it did not already
692 ssa_lazy_cache::set_range (tree name
, const vrange
&r
)
694 unsigned v
= SSA_NAME_VERSION (name
);
695 if (!bitmap_set_bit (active_p
, v
))
697 // There is already an entry, simply set it.
698 gcc_checking_assert (v
< m_tab
.length ());
699 return ssa_cache::set_range (name
, r
);
701 if (v
>= m_tab
.length ())
702 m_tab
.safe_grow (num_ssa_names
+ 1);
703 m_tab
[v
] = m_range_allocator
->clone (r
);
707 // If NAME has a range, intersect it with R, otherwise set it to R.
708 // Return TRUE if the range is new or changes.
711 ssa_lazy_cache::merge_range (tree name
, const vrange
&r
)
713 unsigned v
= SSA_NAME_VERSION (name
);
714 if (!bitmap_set_bit (active_p
, v
))
716 // There is already an entry, simply merge it.
717 gcc_checking_assert (v
< m_tab
.length ());
718 return ssa_cache::merge_range (name
, r
);
720 if (v
>= m_tab
.length ())
721 m_tab
.safe_grow (num_ssa_names
+ 1);
722 m_tab
[v
] = m_range_allocator
->clone (r
);
726 // Return TRUE if NAME has a range, and return it in R.
729 ssa_lazy_cache::get_range (vrange
&r
, tree name
) const
731 if (!bitmap_bit_p (active_p
, SSA_NAME_VERSION (name
)))
733 return ssa_cache::get_range (r
, name
);
736 // Remove NAME from the active range list.
739 ssa_lazy_cache::clear_range (tree name
)
741 bitmap_clear_bit (active_p
, SSA_NAME_VERSION (name
));
744 // Remove all ranges from the active range list.
747 ssa_lazy_cache::clear ()
749 bitmap_clear (active_p
);
752 // --------------------------------------------------------------------------
755 // This class will manage the timestamps for each ssa_name.
756 // When a value is calculated, the timestamp is set to the current time.
757 // Current time is then incremented. Any dependencies will already have
758 // been calculated, and will thus have older timestamps.
759 // If one of those values is ever calculated again, it will get a newer
760 // timestamp, and the "current_p" check will fail.
767 bool current_p (tree name
, tree dep1
, tree dep2
) const;
768 void set_timestamp (tree name
);
769 void set_always_current (tree name
, bool value
);
770 bool always_current_p (tree name
) const;
772 int temporal_value (unsigned ssa
) const;
774 vec
<int> m_timestamp
;
778 temporal_cache::temporal_cache ()
781 m_timestamp
.create (0);
782 m_timestamp
.safe_grow_cleared (num_ssa_names
);
786 temporal_cache::~temporal_cache ()
788 m_timestamp
.release ();
791 // Return the timestamp value for SSA, or 0 if there isn't one.
794 temporal_cache::temporal_value (unsigned ssa
) const
796 if (ssa
>= m_timestamp
.length ())
798 return abs (m_timestamp
[ssa
]);
801 // Return TRUE if the timestamp for NAME is newer than any of its dependents.
802 // Up to 2 dependencies can be checked.
805 temporal_cache::current_p (tree name
, tree dep1
, tree dep2
) const
807 if (always_current_p (name
))
810 // Any non-registered dependencies will have a value of 0 and thus be older.
811 // Return true if time is newer than either dependent.
812 int ts
= temporal_value (SSA_NAME_VERSION (name
));
813 if (dep1
&& ts
< temporal_value (SSA_NAME_VERSION (dep1
)))
815 if (dep2
&& ts
< temporal_value (SSA_NAME_VERSION (dep2
)))
821 // This increments the global timer and sets the timestamp for NAME.
824 temporal_cache::set_timestamp (tree name
)
826 unsigned v
= SSA_NAME_VERSION (name
);
827 if (v
>= m_timestamp
.length ())
828 m_timestamp
.safe_grow_cleared (num_ssa_names
+ 20);
829 m_timestamp
[v
] = ++m_current_time
;
832 // Set the timestamp to 0, marking it as "always up to date".
835 temporal_cache::set_always_current (tree name
, bool value
)
837 unsigned v
= SSA_NAME_VERSION (name
);
838 if (v
>= m_timestamp
.length ())
839 m_timestamp
.safe_grow_cleared (num_ssa_names
+ 20);
841 int ts
= abs (m_timestamp
[v
]);
842 // If this does not have a timestamp, create one.
844 ts
= ++m_current_time
;
845 m_timestamp
[v
] = value
? -ts
: ts
;
848 // Return true if NAME is always current.
851 temporal_cache::always_current_p (tree name
) const
853 unsigned v
= SSA_NAME_VERSION (name
);
854 if (v
>= m_timestamp
.length ())
856 return m_timestamp
[v
] <= 0;
859 // --------------------------------------------------------------------------
861 // This class provides an abstraction of a list of blocks to be updated
862 // by the cache. It is currently a stack but could be changed. It also
863 // maintains a list of blocks which have failed propagation, and does not
864 // enter any of those blocks into the list.
866 // A vector over the BBs is maintained, and an entry of 0 means it is not in
867 // a list. Otherwise, the entry is the next block in the list. -1 terminates
868 // the list. m_head points to the top of the list, -1 if the list is empty.
875 void add (basic_block bb
);
877 inline bool empty_p () { return m_update_head
== -1; }
878 inline void clear_failures () { bitmap_clear (m_propfail
); }
879 inline void propagation_failed (basic_block bb
)
880 { bitmap_set_bit (m_propfail
, bb
->index
); }
882 vec
<int> m_update_list
;
887 // Create an update list.
889 update_list::update_list ()
891 m_update_list
.create (0);
892 m_update_list
.safe_grow_cleared (last_basic_block_for_fn (cfun
) + 64);
894 m_propfail
= BITMAP_ALLOC (NULL
);
897 // Destroy an update list.
899 update_list::~update_list ()
901 m_update_list
.release ();
902 BITMAP_FREE (m_propfail
);
905 // Add BB to the list of blocks to update, unless it's already in the list.
908 update_list::add (basic_block bb
)
911 // If propagation has failed for BB, or its already in the list, don't
913 if ((unsigned)i
>= m_update_list
.length ())
914 m_update_list
.safe_grow_cleared (i
+ 64);
915 if (!m_update_list
[i
] && !bitmap_bit_p (m_propfail
, i
))
920 m_update_list
[i
] = -1;
924 gcc_checking_assert (m_update_head
> 0);
925 m_update_list
[i
] = m_update_head
;
931 // Remove a block from the list.
936 gcc_checking_assert (!empty_p ());
937 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, m_update_head
);
938 int pop
= m_update_head
;
939 m_update_head
= m_update_list
[pop
];
940 m_update_list
[pop
] = 0;
944 // --------------------------------------------------------------------------
946 ranger_cache::ranger_cache (int not_executable_flag
, bool use_imm_uses
)
947 : m_gori (not_executable_flag
),
948 m_exit (use_imm_uses
)
950 m_workback
.create (0);
951 m_workback
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
952 m_workback
.truncate (0);
953 m_temporal
= new temporal_cache
;
954 // If DOM info is available, spawn an oracle as well.
955 if (dom_info_available_p (CDI_DOMINATORS
))
956 m_oracle
= new dom_oracle ();
960 unsigned x
, lim
= last_basic_block_for_fn (cfun
);
961 // Calculate outgoing range info upfront. This will fully populate the
962 // m_maybe_variant bitmap which will help eliminate processing of names
963 // which never have their ranges adjusted.
964 for (x
= 0; x
< lim
; x
++)
966 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, x
);
970 m_update
= new update_list ();
973 ranger_cache::~ranger_cache ()
979 m_workback
.release ();
982 // Dump the global caches to file F. if GORI_DUMP is true, dump the
986 ranger_cache::dump (FILE *f
)
988 fprintf (f
, "Non-varying global ranges:\n");
989 fprintf (f
, "=========================:\n");
994 // Dump the caches for basic block BB to file F.
997 ranger_cache::dump_bb (FILE *f
, basic_block bb
)
999 m_gori
.gori_map::dump (f
, bb
, false);
1000 m_on_entry
.dump (f
, bb
);
1002 m_oracle
->dump (f
, bb
);
1005 // Get the global range for NAME, and return in R. Return false if the
1006 // global range is not set, and return the legacy global value in R.
1009 ranger_cache::get_global_range (vrange
&r
, tree name
) const
1011 if (m_globals
.get_range (r
, name
))
1013 gimple_range_global (r
, name
);
1017 // Get the global range for NAME, and return in R. Return false if the
1018 // global range is not set, and R will contain the legacy global value.
1019 // CURRENT_P is set to true if the value was in cache and not stale.
1020 // Otherwise, set CURRENT_P to false and mark as it always current.
1021 // If the global cache did not have a value, initialize it as well.
1022 // After this call, the global cache will have a value.
1025 ranger_cache::get_global_range (vrange
&r
, tree name
, bool ¤t_p
)
1027 bool had_global
= get_global_range (r
, name
);
1029 // If there was a global value, set current flag, otherwise set a value.
1032 current_p
= r
.singleton_p ()
1033 || m_temporal
->current_p (name
, m_gori
.depend1 (name
),
1034 m_gori
.depend2 (name
));
1037 // If no global value has been set and value is VARYING, fold the stmt
1038 // using just global ranges to get a better initial value.
1039 // After inlining we tend to decide some things are constant, so
1040 // so not do this evaluation after inlining.
1041 if (r
.varying_p () && !cfun
->after_inlining
)
1043 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1044 if (gimple_get_lhs (s
) == name
)
1046 if (!fold_range (r
, s
, get_global_range_query ()))
1047 gimple_range_global (r
, name
);
1050 m_globals
.set_range (name
, r
);
1053 // If the existing value was not current, mark it as always current.
1055 m_temporal
->set_always_current (name
, true);
1059 // Set the global range of NAME to R and give it a timestamp.
1062 ranger_cache::set_global_range (tree name
, const vrange
&r
, bool changed
)
1064 // Setting a range always clears the always_current flag.
1065 m_temporal
->set_always_current (name
, false);
1068 // If there are dependencies, make sure this is not out of date.
1069 if (!m_temporal
->current_p (name
, m_gori
.depend1 (name
),
1070 m_gori
.depend2 (name
)))
1071 m_temporal
->set_timestamp (name
);
1074 if (m_globals
.set_range (name
, r
))
1076 // If there was already a range set, propagate the new value.
1077 basic_block bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
1079 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1081 if (DEBUG_RANGE_CACHE
)
1082 fprintf (dump_file
, " GLOBAL :");
1084 propagate_updated_value (name
, bb
);
1086 // Constants no longer need to tracked. Any further refinement has to be
1087 // undefined. Propagation works better with constants. PR 100512.
1088 // Pointers which resolve to non-zero also do not need
1089 // tracking in the cache as they will never change. See PR 98866.
1090 // Timestamp must always be updated, or dependent calculations may
1091 // not include this latest value. PR 100774.
1093 if (r
.singleton_p ()
1094 || (POINTER_TYPE_P (TREE_TYPE (name
)) && r
.nonzero_p ()))
1095 m_gori
.set_range_invariant (name
);
1096 m_temporal
->set_timestamp (name
);
1099 // Provide lookup for the gori-computes class to access the best known range
1100 // of an ssa_name in any given basic block. Note, this does no additional
1101 // lookups, just accesses the data that is already known.
1103 // Get the range of NAME when the def occurs in block BB. If BB is NULL
1104 // get the best global value available.
1107 ranger_cache::range_of_def (vrange
&r
, tree name
, basic_block bb
)
1109 gcc_checking_assert (gimple_range_ssa_p (name
));
1110 gcc_checking_assert (!bb
|| bb
== gimple_bb (SSA_NAME_DEF_STMT (name
)));
1112 // Pick up the best global range available.
1113 if (!m_globals
.get_range (r
, name
))
1115 // If that fails, try to calculate the range using just global values.
1116 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1117 if (gimple_get_lhs (s
) == name
)
1118 fold_range (r
, s
, get_global_range_query ());
1120 gimple_range_global (r
, name
);
1124 // Get the range of NAME as it occurs on entry to block BB. Use MODE for
1128 ranger_cache::entry_range (vrange
&r
, tree name
, basic_block bb
,
1131 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1133 gimple_range_global (r
, name
);
1137 // Look for the on-entry value of name in BB from the cache.
1138 // Otherwise pick up the best available global value.
1139 if (!m_on_entry
.get_bb_range (r
, name
, bb
))
1140 if (!range_from_dom (r
, name
, bb
, mode
))
1141 range_of_def (r
, name
);
1144 // Get the range of NAME as it occurs on exit from block BB. Use MODE for
1148 ranger_cache::exit_range (vrange
&r
, tree name
, basic_block bb
,
1151 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1153 gimple_range_global (r
, name
);
1157 gimple
*s
= SSA_NAME_DEF_STMT (name
);
1158 basic_block def_bb
= gimple_bb (s
);
1160 range_of_def (r
, name
, bb
);
1162 entry_range (r
, name
, bb
, mode
);
1165 // Get the range of NAME on edge E using MODE, return the result in R.
1166 // Always returns a range and true.
1169 ranger_cache::edge_range (vrange
&r
, edge e
, tree name
, enum rfd_mode mode
)
1171 exit_range (r
, name
, e
->src
, mode
);
1172 // If this is not an abnormal edge, check for inferred ranges on exit.
1173 if ((e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
)) == 0)
1174 m_exit
.maybe_adjust_range (r
, name
, e
->src
);
1175 Value_Range
er (TREE_TYPE (name
));
1176 if (m_gori
.outgoing_edge_range_p (er
, e
, name
, *this))
1183 // Implement range_of_expr.
1186 ranger_cache::range_of_expr (vrange
&r
, tree name
, gimple
*stmt
)
1188 if (!gimple_range_ssa_p (name
))
1190 get_tree_range (r
, name
, stmt
);
1194 basic_block bb
= gimple_bb (stmt
);
1195 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1196 basic_block def_bb
= gimple_bb (def_stmt
);
1199 range_of_def (r
, name
, bb
);
1201 entry_range (r
, name
, bb
, RFD_NONE
);
1206 // Implement range_on_edge. Always return the best available range using
1207 // the current cache values.
1210 ranger_cache::range_on_edge (vrange
&r
, edge e
, tree expr
)
1212 if (gimple_range_ssa_p (expr
))
1213 return edge_range (r
, e
, expr
, RFD_NONE
);
1214 return get_tree_range (r
, expr
, NULL
);
1217 // Return a static range for NAME on entry to basic block BB in R. If
1218 // calc is true, fill any cache entries required between BB and the
1219 // def block for NAME. Otherwise, return false if the cache is empty.
1222 ranger_cache::block_range (vrange
&r
, basic_block bb
, tree name
, bool calc
)
1224 gcc_checking_assert (gimple_range_ssa_p (name
));
1226 // If there are no range calculations anywhere in the IL, global range
1227 // applies everywhere, so don't bother caching it.
1228 if (!m_gori
.has_edge_range_p (name
))
1233 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
1234 basic_block def_bb
= NULL
;
1236 def_bb
= gimple_bb (def_stmt
);;
1239 // If we get to the entry block, this better be a default def
1240 // or range_on_entry was called for a block not dominated by
1242 gcc_checking_assert (SSA_NAME_IS_DEFAULT_DEF (name
));
1243 def_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1246 // There is no range on entry for the definition block.
1250 // Otherwise, go figure out what is known in predecessor blocks.
1251 fill_block_cache (name
, bb
, def_bb
);
1252 gcc_checking_assert (m_on_entry
.bb_range_p (name
, bb
));
1254 return m_on_entry
.get_bb_range (r
, name
, bb
);
1257 // If there is anything in the propagation update_list, continue
1258 // processing NAME until the list of blocks is empty.
1261 ranger_cache::propagate_cache (tree name
)
1266 tree type
= TREE_TYPE (name
);
1267 Value_Range
new_range (type
);
1268 Value_Range
current_range (type
);
1269 Value_Range
e_range (type
);
1271 // Process each block by seeing if its calculated range on entry is
1272 // the same as its cached value. If there is a difference, update
1273 // the cache to reflect the new value, and check to see if any
1274 // successors have cache entries which may need to be checked for
1277 while (!m_update
->empty_p ())
1279 bb
= m_update
->pop ();
1280 gcc_checking_assert (m_on_entry
.bb_range_p (name
, bb
));
1281 m_on_entry
.get_bb_range (current_range
, name
, bb
);
1283 if (DEBUG_RANGE_CACHE
)
1285 fprintf (dump_file
, "FWD visiting block %d for ", bb
->index
);
1286 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1287 fprintf (dump_file
, " starting range : ");
1288 current_range
.dump (dump_file
);
1289 fprintf (dump_file
, "\n");
1292 // Calculate the "new" range on entry by unioning the pred edges.
1293 new_range
.set_undefined ();
1294 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1296 edge_range (e_range
, e
, name
, RFD_READ_ONLY
);
1297 if (DEBUG_RANGE_CACHE
)
1299 fprintf (dump_file
, " edge %d->%d :", e
->src
->index
, bb
->index
);
1300 e_range
.dump (dump_file
);
1301 fprintf (dump_file
, "\n");
1303 new_range
.union_ (e_range
);
1304 if (new_range
.varying_p ())
1308 // If the range on entry has changed, update it.
1309 if (new_range
!= current_range
)
1311 bool ok_p
= m_on_entry
.set_bb_range (name
, bb
, new_range
);
1312 // If the cache couldn't set the value, mark it as failed.
1314 m_update
->propagation_failed (bb
);
1315 if (DEBUG_RANGE_CACHE
)
1319 fprintf (dump_file
, " Cache failure to store value:");
1320 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1321 fprintf (dump_file
, " ");
1325 fprintf (dump_file
, " Updating range to ");
1326 new_range
.dump (dump_file
);
1328 fprintf (dump_file
, "\n Updating blocks :");
1330 // Mark each successor that has a range to re-check its range
1331 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1332 if (m_on_entry
.bb_range_p (name
, e
->dest
))
1334 if (DEBUG_RANGE_CACHE
)
1335 fprintf (dump_file
, " bb%d",e
->dest
->index
);
1336 m_update
->add (e
->dest
);
1338 if (DEBUG_RANGE_CACHE
)
1339 fprintf (dump_file
, "\n");
1342 if (DEBUG_RANGE_CACHE
)
1344 fprintf (dump_file
, "DONE visiting blocks for ");
1345 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1346 fprintf (dump_file
, "\n");
1348 m_update
->clear_failures ();
1351 // Check to see if an update to the value for NAME in BB has any effect
1352 // on values already in the on-entry cache for successor blocks.
1353 // If it does, update them. Don't visit any blocks which don't have a cache
1357 ranger_cache::propagate_updated_value (tree name
, basic_block bb
)
1362 // The update work list should be empty at this point.
1363 gcc_checking_assert (m_update
->empty_p ());
1364 gcc_checking_assert (bb
);
1366 if (DEBUG_RANGE_CACHE
)
1368 fprintf (dump_file
, " UPDATE cache for ");
1369 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1370 fprintf (dump_file
, " in BB %d : successors : ", bb
->index
);
1372 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1374 // Only update active cache entries.
1375 if (m_on_entry
.bb_range_p (name
, e
->dest
))
1377 m_update
->add (e
->dest
);
1378 if (DEBUG_RANGE_CACHE
)
1379 fprintf (dump_file
, " UPDATE: bb%d", e
->dest
->index
);
1382 if (!m_update
->empty_p ())
1384 if (DEBUG_RANGE_CACHE
)
1385 fprintf (dump_file
, "\n");
1386 propagate_cache (name
);
1390 if (DEBUG_RANGE_CACHE
)
1391 fprintf (dump_file
, " : No updates!\n");
1395 // Make sure that the range-on-entry cache for NAME is set for block BB.
1396 // Work back through the CFG to DEF_BB ensuring the range is calculated
1397 // on the block/edges leading back to that point.
1400 ranger_cache::fill_block_cache (tree name
, basic_block bb
, basic_block def_bb
)
1404 tree type
= TREE_TYPE (name
);
1405 Value_Range
block_result (type
);
1406 Value_Range
undefined (type
);
1408 // At this point we shouldn't be looking at the def, entry block.
1409 gcc_checking_assert (bb
!= def_bb
&& bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1410 gcc_checking_assert (m_workback
.length () == 0);
1412 // If the block cache is set, then we've already visited this block.
1413 if (m_on_entry
.bb_range_p (name
, bb
))
1416 if (DEBUG_RANGE_CACHE
)
1418 fprintf (dump_file
, "\n");
1419 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1420 fprintf (dump_file
, " : ");
1423 // Check if a dominators can supply the range.
1424 if (range_from_dom (block_result
, name
, bb
, RFD_FILL
))
1426 if (DEBUG_RANGE_CACHE
)
1428 fprintf (dump_file
, "Filled from dominator! : ");
1429 block_result
.dump (dump_file
);
1430 fprintf (dump_file
, "\n");
1432 // See if any equivalences can refine it.
1433 // PR 109462, like 108139 below, a one way equivalence introduced
1434 // by a PHI node can also be through the definition side. Disallow it.
1439 int prec
= TYPE_PRECISION (type
);
1440 FOR_EACH_PARTIAL_AND_FULL_EQUIV (m_oracle
, bb
, name
, equiv_name
, rel
)
1442 basic_block equiv_bb
= gimple_bb (SSA_NAME_DEF_STMT (equiv_name
));
1444 // Ignore partial equivs that are smaller than this object.
1445 if (rel
!= VREL_EQ
&& prec
> pe_to_bits (rel
))
1448 // Check if the equiv has any ranges calculated.
1449 if (!m_gori
.has_edge_range_p (equiv_name
))
1452 // Check if the equiv definition dominates this block
1453 if (equiv_bb
== bb
||
1454 (equiv_bb
&& !dominated_by_p (CDI_DOMINATORS
, bb
, equiv_bb
)))
1457 if (DEBUG_RANGE_CACHE
)
1460 fprintf (dump_file
, "Checking Equivalence (");
1462 fprintf (dump_file
, "Checking Partial equiv (");
1463 print_relation (dump_file
, rel
);
1464 fprintf (dump_file
, ") ");
1465 print_generic_expr (dump_file
, equiv_name
, TDF_SLIM
);
1466 fprintf (dump_file
, "\n");
1468 Value_Range
equiv_range (TREE_TYPE (equiv_name
));
1469 if (range_from_dom (equiv_range
, equiv_name
, bb
, RFD_READ_ONLY
))
1472 range_cast (equiv_range
, type
);
1474 adjust_equivalence_range (equiv_range
);
1476 if (block_result
.intersect (equiv_range
))
1478 if (DEBUG_RANGE_CACHE
)
1481 fprintf (dump_file
, "Equivalence update! : ");
1483 fprintf (dump_file
, "Partial equiv update! : ");
1484 print_generic_expr (dump_file
, equiv_name
, TDF_SLIM
);
1485 fprintf (dump_file
, " has range : ");
1486 equiv_range
.dump (dump_file
);
1487 fprintf (dump_file
, " refining range to :");
1488 block_result
.dump (dump_file
);
1489 fprintf (dump_file
, "\n");
1496 m_on_entry
.set_bb_range (name
, bb
, block_result
);
1497 gcc_checking_assert (m_workback
.length () == 0);
1501 // Visit each block back to the DEF. Initialize each one to UNDEFINED.
1502 // m_visited at the end will contain all the blocks that we needed to set
1503 // the range_on_entry cache for.
1504 m_workback
.quick_push (bb
);
1505 undefined
.set_undefined ();
1506 m_on_entry
.set_bb_range (name
, bb
, undefined
);
1507 gcc_checking_assert (m_update
->empty_p ());
1509 while (m_workback
.length () > 0)
1511 basic_block node
= m_workback
.pop ();
1512 if (DEBUG_RANGE_CACHE
)
1514 fprintf (dump_file
, "BACK visiting block %d for ", node
->index
);
1515 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1516 fprintf (dump_file
, "\n");
1519 FOR_EACH_EDGE (e
, ei
, node
->preds
)
1521 basic_block pred
= e
->src
;
1522 Value_Range
r (TREE_TYPE (name
));
1524 if (DEBUG_RANGE_CACHE
)
1525 fprintf (dump_file
, " %d->%d ",e
->src
->index
, e
->dest
->index
);
1527 // If the pred block is the def block add this BB to update list.
1530 m_update
->add (node
);
1534 // If the pred is entry but NOT def, then it is used before
1535 // defined, it'll get set to [] and no need to update it.
1536 if (pred
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1538 if (DEBUG_RANGE_CACHE
)
1539 fprintf (dump_file
, "entry: bail.");
1543 // Regardless of whether we have visited pred or not, if the
1544 // pred has inferred ranges, revisit this block.
1545 // Don't search the DOM tree.
1546 if (m_exit
.has_range_p (name
, pred
))
1548 if (DEBUG_RANGE_CACHE
)
1549 fprintf (dump_file
, "Inferred range: update ");
1550 m_update
->add (node
);
1553 // If the pred block already has a range, or if it can contribute
1554 // something new. Ie, the edge generates a range of some sort.
1555 if (m_on_entry
.get_bb_range (r
, name
, pred
))
1557 if (DEBUG_RANGE_CACHE
)
1559 fprintf (dump_file
, "has cache, ");
1561 fprintf (dump_file
, ", ");
1563 if (!r
.undefined_p () || m_gori
.has_edge_range_p (name
, e
))
1565 m_update
->add (node
);
1566 if (DEBUG_RANGE_CACHE
)
1567 fprintf (dump_file
, "update. ");
1572 if (DEBUG_RANGE_CACHE
)
1573 fprintf (dump_file
, "pushing undefined pred block.\n");
1574 // If the pred hasn't been visited (has no range), add it to
1576 gcc_checking_assert (!m_on_entry
.bb_range_p (name
, pred
));
1577 m_on_entry
.set_bb_range (name
, pred
, undefined
);
1578 m_workback
.quick_push (pred
);
1582 if (DEBUG_RANGE_CACHE
)
1583 fprintf (dump_file
, "\n");
1585 // Now fill in the marked blocks with values.
1586 propagate_cache (name
);
1587 if (DEBUG_RANGE_CACHE
)
1588 fprintf (dump_file
, " Propagation update done.\n");
1591 // Resolve the range of BB if the dominators range is R by calculating incoming
1592 // edges to this block. All lead back to the dominator so should be cheap.
1593 // The range for BB is set and returned in R.
1596 ranger_cache::resolve_dom (vrange
&r
, tree name
, basic_block bb
)
1598 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
1599 basic_block dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1601 // if it doesn't already have a value, store the incoming range.
1602 if (!m_on_entry
.bb_range_p (name
, dom_bb
) && def_bb
!= dom_bb
)
1604 // If the range can't be store, don't try to accumulate
1605 // the range in PREV_BB due to excessive recalculations.
1606 if (!m_on_entry
.set_bb_range (name
, dom_bb
, r
))
1609 // With the dominator set, we should be able to cheaply query
1610 // each incoming edge now and accumulate the results.
1614 Value_Range
er (TREE_TYPE (name
));
1615 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1617 // If the predecessor is dominated by this block, then there is a back
1618 // edge, and won't provide anything useful. We'll actually end up with
1619 // VARYING as we will not resolve this node.
1620 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
1622 edge_range (er
, e
, name
, RFD_READ_ONLY
);
1625 // Set the cache in PREV_BB so it is not calculated again.
1626 m_on_entry
.set_bb_range (name
, bb
, r
);
1629 // Get the range of NAME from dominators of BB and return it in R. Search the
1630 // dominator tree based on MODE.
1633 ranger_cache::range_from_dom (vrange
&r
, tree name
, basic_block start_bb
,
1636 if (mode
== RFD_NONE
|| !dom_info_available_p (CDI_DOMINATORS
))
1639 // Search back to the definition block or entry block.
1640 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
1642 def_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
1645 basic_block prev_bb
= start_bb
;
1647 // Track any inferred ranges seen.
1648 Value_Range
infer (TREE_TYPE (name
));
1649 infer
.set_varying (TREE_TYPE (name
));
1651 // Range on entry to the DEF block should not be queried.
1652 gcc_checking_assert (start_bb
!= def_bb
);
1653 unsigned start_limit
= m_workback
.length ();
1655 // Default value is global range.
1656 get_global_range (r
, name
);
1658 // The dominator of EXIT_BLOCK doesn't seem to be set, so at least handle
1659 // the common single exit cases.
1660 if (start_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) && single_pred_p (start_bb
))
1661 bb
= single_pred_edge (start_bb
)->src
;
1663 bb
= get_immediate_dominator (CDI_DOMINATORS
, start_bb
);
1665 // Search until a value is found, pushing blocks which may need calculating.
1666 for ( ; bb
; prev_bb
= bb
, bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1668 // Accumulate any block exit inferred ranges.
1669 m_exit
.maybe_adjust_range (infer
, name
, bb
);
1671 // This block has an outgoing range.
1672 if (m_gori
.has_edge_range_p (name
, bb
))
1673 m_workback
.quick_push (prev_bb
);
1676 // Normally join blocks don't carry any new range information on
1677 // incoming edges. If the first incoming edge to this block does
1678 // generate a range, calculate the ranges if all incoming edges
1679 // are also dominated by the dominator. (Avoids backedges which
1680 // will break the rule of moving only upward in the dominator tree).
1681 // If the first pred does not generate a range, then we will be
1682 // using the dominator range anyway, so that's all the check needed.
1683 if (EDGE_COUNT (prev_bb
->preds
) > 1
1684 && m_gori
.has_edge_range_p (name
, EDGE_PRED (prev_bb
, 0)->src
))
1688 bool all_dom
= true;
1689 FOR_EACH_EDGE (e
, ei
, prev_bb
->preds
)
1691 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
1697 m_workback
.quick_push (prev_bb
);
1704 if (m_on_entry
.get_bb_range (r
, name
, bb
))
1708 if (DEBUG_RANGE_CACHE
)
1710 fprintf (dump_file
, "CACHE: BB %d DOM query for ", start_bb
->index
);
1711 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1712 fprintf (dump_file
, ", found ");
1715 fprintf (dump_file
, " at BB%d\n", bb
->index
);
1717 fprintf (dump_file
, " at function top\n");
1720 // Now process any blocks wit incoming edges that nay have adjustments.
1721 while (m_workback
.length () > start_limit
)
1723 Value_Range
er (TREE_TYPE (name
));
1724 prev_bb
= m_workback
.pop ();
1725 if (!single_pred_p (prev_bb
))
1727 // Non single pred means we need to cache a value in the dominator
1728 // so we can cheaply calculate incoming edges to this block, and
1729 // then store the resulting value. If processing mode is not
1730 // RFD_FILL, then the cache cant be stored to, so don't try.
1731 // Otherwise this becomes a quadratic timed calculation.
1732 if (mode
== RFD_FILL
)
1733 resolve_dom (r
, name
, prev_bb
);
1737 edge e
= single_pred_edge (prev_bb
);
1739 if (m_gori
.outgoing_edge_range_p (er
, e
, name
, *this))
1742 // If this is a normal edge, apply any inferred ranges.
1743 if ((e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
)) == 0)
1744 m_exit
.maybe_adjust_range (r
, name
, bb
);
1746 if (DEBUG_RANGE_CACHE
)
1748 fprintf (dump_file
, "CACHE: Adjusted edge range for %d->%d : ",
1749 bb
->index
, prev_bb
->index
);
1751 fprintf (dump_file
, "\n");
1756 // Apply non-null if appropriate.
1757 if (!has_abnormal_call_or_eh_pred_edge_p (start_bb
))
1758 r
.intersect (infer
);
1760 if (DEBUG_RANGE_CACHE
)
1762 fprintf (dump_file
, "CACHE: Range for DOM returns : ");
1764 fprintf (dump_file
, "\n");
1769 // This routine will register an inferred value in block BB, and possibly
1770 // update the on-entry cache if appropriate.
1773 ranger_cache::register_inferred_value (const vrange
&ir
, tree name
,
1776 Value_Range
r (TREE_TYPE (name
));
1777 if (!m_on_entry
.get_bb_range (r
, name
, bb
))
1778 exit_range (r
, name
, bb
, RFD_READ_ONLY
);
1779 if (r
.intersect (ir
))
1781 m_on_entry
.set_bb_range (name
, bb
, r
);
1782 // If this range was invariant before, remove invariant.
1783 if (!m_gori
.has_edge_range_p (name
))
1784 m_gori
.set_range_invariant (name
, false);
1788 // This routine is used during a block walk to adjust any inferred ranges
1789 // of operands on stmt S.
1792 ranger_cache::apply_inferred_ranges (gimple
*s
)
1796 basic_block bb
= gimple_bb (s
);
1797 gimple_infer_range
infer(s
);
1798 if (infer
.num () == 0)
1801 // Do not update the on-entry cache for block ending stmts.
1802 if (stmt_ends_bb_p (s
))
1806 FOR_EACH_EDGE (e
, ei
, gimple_bb (s
)->succs
)
1807 if (!(e
->flags
& (EDGE_ABNORMAL
|EDGE_EH
)))
1813 for (unsigned x
= 0; x
< infer
.num (); x
++)
1815 tree name
= infer
.name (x
);
1816 m_exit
.add_range (name
, bb
, infer
.range (x
));
1818 register_inferred_value (infer
.range (x
), name
, bb
);