1/* Gimple ranger SSA cache implementation.
2 Copyright (C) 2017-2025 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "backend.h"
25#include "insn-codes.h"
26#include "tree.h"
27#include "gimple.h"
28#include "ssa.h"
29#include "gimple-pretty-print.h"
30#include "gimple-range.h"
31#include "value-range-storage.h"
32#include "tree-cfg.h"
33#include "target.h"
34#include "attribs.h"
35#include "gimple-iterator.h"
36#include "gimple-walk.h"
37#include "cfganal.h"
38
39#define DEBUG_RANGE_CACHE (dump_file \
40 && (param_ranger_debug & RANGER_DEBUG_CACHE))
41
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.
44
45class ssa_block_ranges
46{
47public:
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;
52
53 void dump(FILE *f);
54private:
55 tree m_type;
56};
57
58// Print the list of known ranges for file F in a nice format.
59
60void
61ssa_block_ranges::dump (FILE *f)
62{
63 basic_block bb;
64 value_range r (m_type);
65
66 FOR_EACH_BB_FN (bb, cfun)
67 if (get_bb_range (r, bb))
68 {
69 fprintf (stream: f, format: "BB%d -> ", bb->index);
70 r.dump (f);
71 fprintf (stream: f, format: "\n");
72 }
73}
74
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.
78
79class sbr_vector : public ssa_block_ranges
80{
81public:
82 sbr_vector (tree t, vrange_allocator *allocator, bool zero_p = true);
83
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;
87protected:
88 vrange_storage **m_tab; // Non growing vector.
89 int m_tab_size;
90 vrange_storage *m_varying;
91 vrange_storage *m_undefined;
92 tree m_type;
93 vrange_allocator *m_range_allocator;
94 bool m_zero_p;
95 void grow ();
96};
97
98
99// Initialize a block cache for an ssa_name of type T.
100
101sbr_vector::sbr_vector (tree t, vrange_allocator *allocator, bool zero_p)
102 : ssa_block_ranges (t)
103{
104 gcc_checking_assert (TYPE_P (t));
105 m_type = t;
106 m_zero_p = zero_p;
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 (size: m_tab_size * sizeof (vrange_storage *)));
111 if (zero_p)
112 memset (s: m_tab, c: 0, n: m_tab_size * sizeof (vrange *));
113
114 // Create the cached type range.
115 m_varying = m_range_allocator->clone_varying (type: t);
116 m_undefined = m_range_allocator->clone_undefined (type: t);
117}
118
119// Grow the vector when the CFG has increased in size.
120
121void
122sbr_vector::grow ()
123{
124 int curr_bb_size = last_basic_block_for_fn (cfun);
125 gcc_checking_assert (curr_bb_size > m_tab_size);
126
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;
131
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 (size: new_size * sizeof (vrange_storage *)));
135 memcpy (dest: t, src: m_tab, n: m_tab_size * sizeof (vrange_storage *));
136 if (m_zero_p)
137 memset (s: t + m_tab_size, c: 0, n: (new_size - m_tab_size) * sizeof (vrange_storage *));
138
139 m_tab = t;
140 m_tab_size = new_size;
141}
142
143// Set the range for block BB to be R.
144
145bool
146sbr_vector::set_bb_range (const_basic_block bb, const vrange &r)
147{
148 vrange_storage *m;
149 if (bb->index >= m_tab_size)
150 grow ();
151 if (r.varying_p ())
152 m = m_varying;
153 else if (r.undefined_p ())
154 m = m_undefined;
155 else
156 m = m_range_allocator->clone (r);
157 m_tab[bb->index] = m;
158 return true;
159}
160
161// Return the range associated with block BB in R. Return false if
162// there is no range.
163
164bool
165sbr_vector::get_bb_range (vrange &r, const_basic_block bb)
166{
167 if (bb->index >= m_tab_size)
168 return false;
169 vrange_storage *m = m_tab[bb->index];
170 if (m)
171 {
172 m->get_vrange (r, type: m_type);
173 return true;
174 }
175 return false;
176}
177
178// Return true if a range is present.
179
180bool
181sbr_vector::bb_range_p (const_basic_block bb)
182{
183 if (bb->index < m_tab_size)
184 return m_tab[bb->index] != NULL;
185 return false;
186}
187
188// Like an sbr_vector, except it uses a bitmap to manage whetehr vale is set
189// or not rather than cleared memory.
190
191class sbr_lazy_vector : public sbr_vector
192{
193public:
194 sbr_lazy_vector (tree t, vrange_allocator *allocator, bitmap_obstack *bm);
195
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;
199protected:
200 bitmap m_has_value;
201};
202
203sbr_lazy_vector::sbr_lazy_vector (tree t, vrange_allocator *allocator,
204 bitmap_obstack *bm)
205 : sbr_vector (t, allocator, false)
206{
207 m_has_value = BITMAP_ALLOC (obstack: bm);
208}
209
210bool
211sbr_lazy_vector::set_bb_range (const_basic_block bb, const vrange &r)
212{
213 sbr_vector::set_bb_range (bb, r);
214 bitmap_set_bit (m_has_value, bb->index);
215 return true;
216}
217
218bool
219sbr_lazy_vector::get_bb_range (vrange &r, const_basic_block bb)
220{
221 if (bitmap_bit_p (m_has_value, bb->index))
222 return sbr_vector::get_bb_range (r, bb);
223 return false;
224}
225
226bool
227sbr_lazy_vector::bb_range_p (const_basic_block bb)
228{
229 return bitmap_bit_p (m_has_value, bb->index);
230}
231
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]
240
241#define SBR_NUM 14
242#define SBR_UNDEF SBR_NUM + 1
243#define SBR_VARYING 1
244
245class sbr_sparse_bitmap : public ssa_block_ranges
246{
247public:
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;
252private:
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];
257 bitmap_head bitvec;
258 tree m_type;
259};
260
261// Initialize a block cache for an ssa_name of type T.
262
263sbr_sparse_bitmap::sbr_sparse_bitmap (tree t, vrange_allocator *allocator,
264 bitmap_obstack *bm)
265 : ssa_block_ranges (t)
266{
267 gcc_checking_assert (TYPE_P (t));
268 m_type = t;
269 bitmap_initialize (head: &bitvec, obstack: bm);
270 bitmap_tree_view (&bitvec);
271 m_range_allocator = allocator;
272 // Pre-cache varying.
273 m_range[0] = m_range_allocator->clone_varying (type: t);
274 // Pre-cache zero and non-zero values for pointers.
275 if (POINTER_TYPE_P (t))
276 {
277 prange nonzero;
278 nonzero.set_nonzero (t);
279 m_range[1] = m_range_allocator->clone (r: nonzero);
280 prange zero;
281 zero.set_zero (t);
282 m_range[2] = m_range_allocator->clone (r: zero);
283 }
284 else
285 m_range[1] = m_range[2] = NULL;
286 // Clear SBR_NUM entries.
287 for (int x = 3; x < SBR_NUM; x++)
288 m_range[x] = 0;
289}
290
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.
294
295inline void
296sbr_sparse_bitmap::bitmap_set_quad (bitmap head, int quad, int quad_value)
297{
298 bitmap_set_aligned_chunk (head, quad, 4, (BITMAP_WORD) quad_value);
299}
300
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.
304inline int
305sbr_sparse_bitmap::bitmap_get_quad (const_bitmap head, int quad)
306{
307 return (int) bitmap_get_aligned_chunk (head, quad, 4);
308}
309
310// Set the range on entry to basic block BB to R.
311
312bool
313sbr_sparse_bitmap::set_bb_range (const_basic_block bb, const vrange &r)
314{
315 if (r.undefined_p ())
316 {
317 bitmap_set_quad (head: &bitvec, quad: bb->index, SBR_UNDEF);
318 return true;
319 }
320
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))
324 {
325 if (!m_range[x])
326 m_range[x] = m_range_allocator->clone (r);
327 bitmap_set_quad (head: &bitvec, quad: bb->index, quad_value: x + 1);
328 return true;
329 }
330 // All values are taken, default to VARYING.
331 bitmap_set_quad (head: &bitvec, quad: bb->index, SBR_VARYING);
332 return false;
333}
334
335// Return the range associated with block BB in R. Return false if
336// there is no range.
337
338bool
339sbr_sparse_bitmap::get_bb_range (vrange &r, const_basic_block bb)
340{
341 int value = bitmap_get_quad (head: &bitvec, quad: bb->index);
342
343 if (!value)
344 return false;
345
346 gcc_checking_assert (value <= SBR_UNDEF);
347 if (value == SBR_UNDEF)
348 r.set_undefined ();
349 else
350 m_range[value - 1]->get_vrange (r, type: m_type);
351 return true;
352}
353
354// Return true if a range is present.
355
356bool
357sbr_sparse_bitmap::bb_range_p (const_basic_block bb)
358{
359 return (bitmap_get_quad (head: &bitvec, quad: bb->index) != 0);
360}
361
362// -------------------------------------------------------------------------
363
364// Initialize the block cache.
365
366block_range_cache::block_range_cache ()
367{
368 bitmap_obstack_initialize (&m_bitmaps);
369 m_ssa_ranges.create (nelems: 0);
370 m_ssa_ranges.safe_grow_cleared (num_ssa_names);
371 m_range_allocator = new vrange_allocator;
372}
373
374// Remove any m_block_caches which have been created.
375
376block_range_cache::~block_range_cache ()
377{
378 delete m_range_allocator;
379 // Release the vector itself.
380 m_ssa_ranges.release ();
381 bitmap_obstack_release (&m_bitmaps);
382}
383
384// Set the range for NAME on entry to block BB to R.
385// If it has not been accessed yet, allocate it first.
386
387bool
388block_range_cache::set_bb_range (tree name, const_basic_block bb,
389 const vrange &r)
390{
391 unsigned v = SSA_NAME_VERSION (name);
392 if (v >= m_ssa_ranges.length ())
393 m_ssa_ranges.safe_grow_cleared (num_ssa_names);
394
395 if (!m_ssa_ranges[v])
396 {
397 // Use sparse bitmap representation if there are too many basic blocks.
398 if (last_basic_block_for_fn (cfun) > param_vrp_sparse_threshold)
399 {
400 void *r = m_range_allocator->alloc (size: sizeof (sbr_sparse_bitmap));
401 m_ssa_ranges[v] = new (r) sbr_sparse_bitmap (TREE_TYPE (name),
402 m_range_allocator,
403 &m_bitmaps);
404 }
405 else if (last_basic_block_for_fn (cfun) < param_vrp_vector_threshold)
406 {
407 // For small CFGs use the basic vector implemntation.
408 void *r = m_range_allocator->alloc (size: sizeof (sbr_vector));
409 m_ssa_ranges[v] = new (r) sbr_vector (TREE_TYPE (name),
410 m_range_allocator);
411 }
412 else
413 {
414 // Otherwise use the sparse vector implementation.
415 void *r = m_range_allocator->alloc (size: sizeof (sbr_lazy_vector));
416 m_ssa_ranges[v] = new (r) sbr_lazy_vector (TREE_TYPE (name),
417 m_range_allocator,
418 &m_bitmaps);
419 }
420 }
421 return m_ssa_ranges[v]->set_bb_range (bb, r);
422}
423
424
425// Return a pointer to the ssa_block_cache for NAME. If it has not been
426// accessed yet, return NULL.
427
428inline ssa_block_ranges *
429block_range_cache::query_block_ranges (tree name)
430{
431 unsigned v = SSA_NAME_VERSION (name);
432 if (v >= m_ssa_ranges.length () || !m_ssa_ranges[v])
433 return NULL;
434 return m_ssa_ranges[v];
435}
436
437
438
439// Return the range for NAME on entry to BB in R. Return true if there
440// is one.
441
442bool
443block_range_cache::get_bb_range (vrange &r, tree name, const_basic_block bb)
444{
445 ssa_block_ranges *ptr = query_block_ranges (name);
446 if (ptr)
447 return ptr->get_bb_range (r, bb);
448 return false;
449}
450
451// Return true if NAME has a range set in block BB.
452
453bool
454block_range_cache::bb_range_p (tree name, const_basic_block bb)
455{
456 ssa_block_ranges *ptr = query_block_ranges (name);
457 if (ptr)
458 return ptr->bb_range_p (bb);
459 return false;
460}
461
462// Print all known block caches to file F.
463
464void
465block_range_cache::dump (FILE *f)
466{
467 unsigned x;
468 for (x = 1; x < m_ssa_ranges.length (); ++x)
469 {
470 if (m_ssa_ranges[x])
471 {
472 fprintf (stream: f, format: " Ranges for ");
473 print_generic_expr (f, ssa_name (x), TDF_NONE);
474 fprintf (stream: f, format: ":\n");
475 m_ssa_ranges[x]->dump (f);
476 fprintf (stream: f, format: "\n");
477 }
478 }
479}
480
481// Print all known ranges on entry to block BB to file F.
482
483void
484block_range_cache::dump (FILE *f, basic_block bb, bool print_varying)
485{
486 unsigned x;
487 bool summarize_varying = false;
488 for (x = 1; x < m_ssa_ranges.length (); ++x)
489 {
490 if (!m_ssa_ranges[x])
491 continue;
492
493 if (!gimple_range_ssa_p (ssa_name (x)))
494 continue;
495
496 value_range r (TREE_TYPE (ssa_name (x)));
497 if (m_ssa_ranges[x]->get_bb_range (r, bb))
498 {
499 if (!print_varying && r.varying_p ())
500 {
501 summarize_varying = true;
502 continue;
503 }
504 print_generic_expr (f, ssa_name (x), TDF_NONE);
505 fprintf (stream: f, format: "\t");
506 r.dump(f);
507 fprintf (stream: f, format: "\n");
508 }
509 }
510 // If there were any varying entries, lump them all together.
511 if (summarize_varying)
512 {
513 fprintf (stream: f, format: "VARYING_P on entry : ");
514 for (x = 1; x < m_ssa_ranges.length (); ++x)
515 {
516 if (!m_ssa_ranges[x])
517 continue;
518
519 if (!gimple_range_ssa_p (ssa_name (x)))
520 continue;
521
522 value_range r (TREE_TYPE (ssa_name (x)));
523 if (m_ssa_ranges[x]->get_bb_range (r, bb))
524 {
525 if (r.varying_p ())
526 {
527 print_generic_expr (f, ssa_name (x), TDF_NONE);
528 fprintf (stream: f, format: " ");
529 }
530 }
531 }
532 fprintf (stream: f, format: "\n");
533 }
534}
535
536// -------------------------------------------------------------------------
537
538// Initialize an ssa cache.
539
540ssa_cache::ssa_cache ()
541{
542 m_tab.create (nelems: 0);
543 m_range_allocator = new vrange_allocator;
544}
545
546// Deconstruct an ssa cache.
547
548ssa_cache::~ssa_cache ()
549{
550 m_tab.release ();
551 delete m_range_allocator;
552}
553
554// Enable a query to evaluate staements/ramnges based on picking up ranges
555// from just an ssa-cache.
556
557bool
558ssa_cache::range_of_expr (vrange &r, tree expr, gimple *stmt)
559{
560 if (!gimple_range_ssa_p (exp: expr))
561 return get_tree_range (v&: r, expr, stmt);
562
563 if (!get_range (r, name: expr))
564 gimple_range_global (v&: r, name: expr, cfun);
565 return true;
566}
567
568// Return TRUE if the global range of NAME has a cache entry.
569
570bool
571ssa_cache::has_range (tree name) const
572{
573 unsigned v = SSA_NAME_VERSION (name);
574 if (v >= m_tab.length ())
575 return false;
576 return m_tab[v] != NULL;
577}
578
579// Retrieve the global range of NAME from cache memory if it exists.
580// Return the value in R.
581
582bool
583ssa_cache::get_range (vrange &r, tree name) const
584{
585 unsigned v = SSA_NAME_VERSION (name);
586 if (v >= m_tab.length ())
587 return false;
588
589 vrange_storage *stow = m_tab[v];
590 if (!stow)
591 return false;
592 stow->get_vrange (r, TREE_TYPE (name));
593 return true;
594}
595
596// Set the range for NAME to R in the ssa cache.
597// Return TRUE if there was already a range set, otherwise false.
598
599bool
600ssa_cache::set_range (tree name, const vrange &r)
601{
602 unsigned v = SSA_NAME_VERSION (name);
603 if (v >= m_tab.length ())
604 m_tab.safe_grow_cleared (num_ssa_names + 1);
605
606 vrange_storage *m = m_tab[v];
607 if (m && m->fits_p (r))
608 m->set_vrange (r);
609 else
610 m_tab[v] = m_range_allocator->clone (r);
611 return m != NULL;
612}
613
614// If NAME has a range, intersect it with R, otherwise set it to R.
615// Return TRUE if the range is new or changes.
616
617bool
618ssa_cache::merge_range (tree name, const vrange &r)
619{
620 unsigned v = SSA_NAME_VERSION (name);
621 if (v >= m_tab.length ())
622 m_tab.safe_grow_cleared (num_ssa_names + 1);
623
624 vrange_storage *m = m_tab[v];
625 // Check if this is a new value.
626 if (!m)
627 m_tab[v] = m_range_allocator->clone (r);
628 else
629 {
630 value_range curr (TREE_TYPE (name));
631 m->get_vrange (r&: curr, TREE_TYPE (name));
632 // If there is no change, return false.
633 if (!curr.intersect (r))
634 return false;
635
636 if (m->fits_p (r: curr))
637 m->set_vrange (curr);
638 else
639 m_tab[v] = m_range_allocator->clone (r: curr);
640 }
641 return true;
642}
643
644// Set the range for NAME to R in the ssa cache.
645
646void
647ssa_cache::clear_range (tree name)
648{
649 unsigned v = SSA_NAME_VERSION (name);
650 if (v >= m_tab.length ())
651 return;
652 m_tab[v] = NULL;
653}
654
655// Clear the ssa cache.
656
657void
658ssa_cache::clear ()
659{
660 if (m_tab.address ())
661 memset (s: m_tab.address(), c: 0, n: m_tab.length () * sizeof (vrange *));
662}
663
664// Dump the contents of the ssa cache to F.
665
666void
667ssa_cache::dump (FILE *f)
668{
669 for (unsigned x = 1; x < num_ssa_names; x++)
670 {
671 if (!gimple_range_ssa_p (ssa_name (x)))
672 continue;
673 value_range r (TREE_TYPE (ssa_name (x)));
674 // Dump all non-varying ranges.
675 if (get_range (r, ssa_name (x)) && !r.varying_p ())
676 {
677 print_generic_expr (f, ssa_name (x), TDF_NONE);
678 fprintf (stream: f, format: " : ");
679 r.dump (f);
680 fprintf (stream: f, format: "\n");
681 }
682 }
683
684}
685
686// Construct an ssa_lazy_cache. If OB is specified, us it, otherwise use
687// a local bitmap obstack.
688
689ssa_lazy_cache::ssa_lazy_cache (bitmap_obstack *ob)
690{
691 if (!ob)
692 {
693 bitmap_obstack_initialize (&m_bitmaps);
694 m_ob = &m_bitmaps;
695 }
696 else
697 m_ob = ob;
698 active_p = BITMAP_ALLOC (obstack: m_ob);
699}
700
701// Destruct an sa_lazy_cache. Free the bitmap if it came from a different
702// obstack, or release the obstack if it was a local one.
703
704ssa_lazy_cache::~ssa_lazy_cache ()
705{
706 if (m_ob == &m_bitmaps)
707 bitmap_obstack_release (&m_bitmaps);
708 else
709 BITMAP_FREE (active_p);
710}
711
712// Return true if NAME has an active range in the cache.
713
714bool
715ssa_lazy_cache::has_range (tree name) const
716{
717 return bitmap_bit_p (active_p, SSA_NAME_VERSION (name));
718}
719
720// Set range of NAME to R in a lazy cache. Return FALSE if it did not already
721// have a range.
722
723bool
724ssa_lazy_cache::set_range (tree name, const vrange &r)
725{
726 unsigned v = SSA_NAME_VERSION (name);
727 if (!bitmap_set_bit (active_p, v))
728 {
729 // There is already an entry, simply set it.
730 gcc_checking_assert (v < m_tab.length ());
731 return ssa_cache::set_range (name, r);
732 }
733 if (v >= m_tab.length ())
734 m_tab.safe_grow (num_ssa_names + 1);
735 m_tab[v] = m_range_allocator->clone (r);
736 return false;
737}
738
739// If NAME has a range, intersect it with R, otherwise set it to R.
740// Return TRUE if the range is new or changes.
741
742bool
743ssa_lazy_cache::merge_range (tree name, const vrange &r)
744{
745 unsigned v = SSA_NAME_VERSION (name);
746 if (!bitmap_set_bit (active_p, v))
747 {
748 // There is already an entry, simply merge it.
749 gcc_checking_assert (v < m_tab.length ());
750 return ssa_cache::merge_range (name, r);
751 }
752 if (v >= m_tab.length ())
753 m_tab.safe_grow (num_ssa_names + 1);
754 m_tab[v] = m_range_allocator->clone (r);
755 return true;
756}
757
758// Merge all elements of CACHE with this cache.
759// Any names in CACHE that are not in this one are added.
760// Any names in both are merged via merge_range..
761
762void
763ssa_lazy_cache::merge (const ssa_lazy_cache &cache)
764{
765 unsigned x;
766 bitmap_iterator bi;
767 EXECUTE_IF_SET_IN_BITMAP (cache.active_p, 0, x, bi)
768 {
769 tree name = ssa_name (x);
770 value_range r(TREE_TYPE (name));
771 cache.get_range (r, name);
772 merge_range (ssa_name (x), r);
773 }
774}
775
776// Return TRUE if NAME has a range, and return it in R.
777
778bool
779ssa_lazy_cache::get_range (vrange &r, tree name) const
780{
781 if (!bitmap_bit_p (active_p, SSA_NAME_VERSION (name)))
782 return false;
783 return ssa_cache::get_range (r, name);
784}
785
786// Remove NAME from the active range list.
787
788void
789ssa_lazy_cache::clear_range (tree name)
790{
791 bitmap_clear_bit (active_p, SSA_NAME_VERSION (name));
792}
793
794// Remove all ranges from the active range list.
795
796void
797ssa_lazy_cache::clear ()
798{
799 bitmap_clear (active_p);
800}
801
802// --------------------------------------------------------------------------
803
804
805// This class will manage the timestamps for each ssa_name.
806// When a value is calculated, the timestamp is set to the current time.
807// Current time is then incremented. Any dependencies will already have
808// been calculated, and will thus have older timestamps.
809// If one of those values is ever calculated again, it will get a newer
810// timestamp, and the "current_p" check will fail.
811
812class temporal_cache
813{
814public:
815 temporal_cache ();
816 ~temporal_cache ();
817 bool current_p (tree name, tree dep1, tree dep2) const;
818 void set_timestamp (tree name);
819 void set_always_current (tree name, bool value);
820 bool always_current_p (tree name) const;
821private:
822 int temporal_value (unsigned ssa) const;
823 int m_current_time;
824 vec <int> m_timestamp;
825};
826
827inline
828temporal_cache::temporal_cache ()
829{
830 m_current_time = 1;
831 m_timestamp.create (nelems: 0);
832 m_timestamp.safe_grow_cleared (num_ssa_names);
833}
834
835inline
836temporal_cache::~temporal_cache ()
837{
838 m_timestamp.release ();
839}
840
841// Return the timestamp value for SSA, or 0 if there isn't one.
842
843inline int
844temporal_cache::temporal_value (unsigned ssa) const
845{
846 if (ssa >= m_timestamp.length ())
847 return 0;
848 return abs (x: m_timestamp[ssa]);
849}
850
851// Return TRUE if the timestamp for NAME is newer than any of its dependents.
852// Up to 2 dependencies can be checked.
853
854bool
855temporal_cache::current_p (tree name, tree dep1, tree dep2) const
856{
857 if (always_current_p (name))
858 return true;
859
860 // Any non-registered dependencies will have a value of 0 and thus be older.
861 // Return true if time is newer than either dependent.
862 int ts = temporal_value (SSA_NAME_VERSION (name));
863 if (dep1 && ts < temporal_value (SSA_NAME_VERSION (dep1)))
864 return false;
865 if (dep2 && ts < temporal_value (SSA_NAME_VERSION (dep2)))
866 return false;
867
868 return true;
869}
870
871// This increments the global timer and sets the timestamp for NAME.
872
873inline void
874temporal_cache::set_timestamp (tree name)
875{
876 unsigned v = SSA_NAME_VERSION (name);
877 if (v >= m_timestamp.length ())
878 m_timestamp.safe_grow_cleared (num_ssa_names + 20);
879 m_timestamp[v] = ++m_current_time;
880}
881
882// Set the timestamp to 0, marking it as "always up to date".
883
884inline void
885temporal_cache::set_always_current (tree name, bool value)
886{
887 unsigned v = SSA_NAME_VERSION (name);
888 if (v >= m_timestamp.length ())
889 m_timestamp.safe_grow_cleared (num_ssa_names + 20);
890
891 int ts = abs (x: m_timestamp[v]);
892 // If this does not have a timestamp, create one.
893 if (ts == 0)
894 ts = ++m_current_time;
895 m_timestamp[v] = value ? -ts : ts;
896}
897
898// Return true if NAME is always current.
899
900inline bool
901temporal_cache::always_current_p (tree name) const
902{
903 unsigned v = SSA_NAME_VERSION (name);
904 if (v >= m_timestamp.length ())
905 return false;
906 return m_timestamp[v] <= 0;
907}
908
909// --------------------------------------------------------------------------
910
911// This class provides an abstraction of a list of blocks to be updated
912// by the cache. It is currently a stack but could be changed. It also
913// maintains a list of blocks which have failed propagation, and does not
914// enter any of those blocks into the list.
915
916// A vector over the BBs is maintained, and an entry of 0 means it is not in
917// a list. Otherwise, the entry is the next block in the list. -1 terminates
918// the list. m_head points to the top of the list, -1 if the list is empty.
919
920class update_list
921{
922public:
923 update_list ();
924 ~update_list ();
925 void add (basic_block bb);
926 basic_block pop ();
927 inline bool empty_p () { return m_update_head == -1; }
928 inline void clear_failures () { bitmap_clear (m_propfail); }
929 inline void propagation_failed (basic_block bb)
930 { bitmap_set_bit (m_propfail, bb->index); }
931private:
932 vec<int> m_update_list;
933 int m_update_head;
934 bitmap m_propfail;
935 bitmap_obstack m_bitmaps;
936};
937
938// Create an update list.
939
940update_list::update_list ()
941{
942 m_update_list.create (nelems: 0);
943 m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun) + 64);
944 m_update_head = -1;
945 bitmap_obstack_initialize (&m_bitmaps);
946 m_propfail = BITMAP_ALLOC (obstack: &m_bitmaps);
947}
948
949// Destroy an update list.
950
951update_list::~update_list ()
952{
953 m_update_list.release ();
954 bitmap_obstack_release (&m_bitmaps);
955}
956
957// Add BB to the list of blocks to update, unless it's already in the list.
958
959void
960update_list::add (basic_block bb)
961{
962 int i = bb->index;
963 // If propagation has failed for BB, or its already in the list, don't
964 // add it again.
965 if ((unsigned)i >= m_update_list.length ())
966 m_update_list.safe_grow_cleared (len: i + 64);
967 if (!m_update_list[i] && !bitmap_bit_p (m_propfail, i))
968 {
969 if (empty_p ())
970 {
971 m_update_head = i;
972 m_update_list[i] = -1;
973 }
974 else
975 {
976 gcc_checking_assert (m_update_head > 0);
977 m_update_list[i] = m_update_head;
978 m_update_head = i;
979 }
980 }
981}
982
983// Remove a block from the list.
984
985basic_block
986update_list::pop ()
987{
988 gcc_checking_assert (!empty_p ());
989 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, m_update_head);
990 int pop = m_update_head;
991 m_update_head = m_update_list[pop];
992 m_update_list[pop] = 0;
993 return bb;
994}
995
996// --------------------------------------------------------------------------
997
998ranger_cache::ranger_cache (int not_executable_flag, bool use_imm_uses)
999{
1000 m_workback = vNULL;
1001 m_temporal = new temporal_cache;
1002
1003 // If DOM info is available, spawn an oracle as well.
1004 create_relation_oracle ();
1005 // Create an infer oracle using this cache as the range query. The cache
1006 // version acts as a read-only query, and will spawn no additional lookups.
1007 // It just ues what is already known.
1008 create_infer_oracle (q: this, do_search: use_imm_uses);
1009 create_gori (not_executable_flag, param_vrp_switch_limit);
1010
1011 unsigned x, lim = last_basic_block_for_fn (cfun);
1012 // Calculate outgoing range info upfront. This will fully populate the
1013 // m_maybe_variant bitmap which will help eliminate processing of names
1014 // which never have their ranges adjusted.
1015 for (x = 0; x < lim ; x++)
1016 {
1017 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, x);
1018 if (bb)
1019 gori_ssa ()->exports (bb);
1020 }
1021 m_update = new update_list ();
1022}
1023
1024ranger_cache::~ranger_cache ()
1025{
1026 delete m_update;
1027 destroy_infer_oracle ();
1028 destroy_relation_oracle ();
1029 delete m_temporal;
1030 m_workback.release ();
1031}
1032
1033// Dump the global caches to file F. if GORI_DUMP is true, dump the
1034// gori map as well.
1035
1036void
1037ranger_cache::dump (FILE *f)
1038{
1039 fprintf (stream: f, format: "Non-varying global ranges:\n");
1040 fprintf (stream: f, format: "=========================:\n");
1041 m_globals.dump (f);
1042 fprintf (stream: f, format: "\n");
1043}
1044
1045// Dump the caches for basic block BB to file F.
1046
1047void
1048ranger_cache::dump_bb (FILE *f, basic_block bb)
1049{
1050 gori_ssa ()->dump (f, bb, verbose: false);
1051 m_on_entry.dump (f, bb);
1052 m_relation->dump (f, bb);
1053}
1054
1055// Get the global range for NAME, and return in R. Return false if the
1056// global range is not set, and return the legacy global value in R.
1057
1058bool
1059ranger_cache::get_global_range (vrange &r, tree name) const
1060{
1061 if (m_globals.get_range (r, name))
1062 return true;
1063 gimple_range_global (v&: r, name);
1064 return false;
1065}
1066
1067// Get the global range for NAME, and return in R. Return false if the
1068// global range is not set, and R will contain the legacy global value.
1069// CURRENT_P is set to true if the value was in cache and not stale.
1070// Otherwise, set CURRENT_P to false and mark as it always current.
1071// If the global cache did not have a value, initialize it as well.
1072// After this call, the global cache will have a value.
1073
1074bool
1075ranger_cache::get_global_range (vrange &r, tree name, bool &current_p)
1076{
1077 bool had_global = get_global_range (r, name);
1078
1079 // If there was a global value, set current flag, otherwise set a value.
1080 current_p = false;
1081 if (had_global)
1082 current_p = r.singleton_p ()
1083 || m_temporal->current_p (name, dep1: gori_ssa ()->depend1 (name),
1084 dep2: gori_ssa ()->depend2 (name));
1085 else
1086 {
1087 // If no global value has been set and value is VARYING, fold the stmt
1088 // using just global ranges to get a better initial value.
1089 // After inlining we tend to decide some things are constant, so
1090 // so not do this evaluation after inlining.
1091 if (r.varying_p () && !cfun->after_inlining)
1092 {
1093 gimple *s = SSA_NAME_DEF_STMT (name);
1094 // Do not process PHIs as SCEV may be in use and it can
1095 // spawn cyclic lookups.
1096 if (gimple_get_lhs (s) == name && !is_a<gphi *> (p: s))
1097 {
1098 if (!fold_range (r, s, q: get_global_range_query ()))
1099 gimple_range_global (v&: r, name);
1100 }
1101 }
1102 m_globals.set_range (name, r);
1103 }
1104
1105 // If the existing value was not current, mark it as always current.
1106 if (!current_p)
1107 m_temporal->set_always_current (name, value: true);
1108 return had_global;
1109}
1110
1111// Set the global range of NAME to R and give it a timestamp.
1112
1113void
1114ranger_cache::set_global_range (tree name, const vrange &r, bool changed)
1115{
1116 // Setting a range always clears the always_current flag.
1117 m_temporal->set_always_current (name, value: false);
1118 if (!changed)
1119 {
1120 // If there are dependencies, make sure this is not out of date.
1121 if (!m_temporal->current_p (name, dep1: gori_ssa ()->depend1 (name),
1122 dep2: gori_ssa ()->depend2 (name)))
1123 m_temporal->set_timestamp (name);
1124 return;
1125 }
1126 if (m_globals.set_range (name, r))
1127 {
1128 // If there was already a range set, propagate the new value.
1129 basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1130 if (!bb)
1131 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1132
1133 if (DEBUG_RANGE_CACHE)
1134 fprintf (stream: dump_file, format: " GLOBAL :");
1135
1136 propagate_updated_value (name, bb);
1137 }
1138 // Constants no longer need to tracked. Any further refinement has to be
1139 // undefined. Propagation works better with constants. PR 100512.
1140 // Pointers which resolve to non-zero also do not need
1141 // tracking in the cache as they will never change. See PR 98866.
1142 // Timestamp must always be updated, or dependent calculations may
1143 // not include this latest value. PR 100774.
1144
1145 if (r.singleton_p ()
1146 || (POINTER_TYPE_P (TREE_TYPE (name)) && r.nonzero_p ()))
1147 gori_ssa ()->set_range_invariant (name);
1148 m_temporal->set_timestamp (name);
1149}
1150
1151// Provide lookup for the gori-computes class to access the best known range
1152// of an ssa_name in any given basic block. Note, this does no additional
1153// lookups, just accesses the data that is already known.
1154
1155// Get the range of NAME when the def occurs in block BB. If BB is NULL
1156// get the best global value available.
1157
1158void
1159ranger_cache::range_of_def (vrange &r, tree name, basic_block bb)
1160{
1161 gcc_checking_assert (gimple_range_ssa_p (name));
1162 gcc_checking_assert (!bb || bb == gimple_bb (SSA_NAME_DEF_STMT (name)));
1163
1164 // Pick up the best global range available.
1165 if (!m_globals.get_range (r, name))
1166 {
1167 // If that fails, try to calculate the range using just global values.
1168 gimple *s = SSA_NAME_DEF_STMT (name);
1169 if (gimple_get_lhs (s) == name)
1170 fold_range (r, s, q: get_global_range_query ());
1171 else
1172 gimple_range_global (v&: r, name);
1173 }
1174}
1175
1176// Get the range of NAME as it occurs on entry to block BB. Use MODE for
1177// lookups.
1178
1179void
1180ranger_cache::entry_range (vrange &r, tree name, basic_block bb,
1181 enum rfd_mode mode)
1182{
1183 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1184 {
1185 gimple_range_global (v&: r, name);
1186 return;
1187 }
1188
1189 // If NAME is invariant, simply return the defining range.
1190 if (!gori ().has_edge_range_p (name))
1191 {
1192 range_of_def (r, name);
1193 return;
1194 }
1195
1196 // Look for the on-entry value of name in BB from the cache.
1197 // Otherwise pick up the best available global value.
1198 if (!m_on_entry.get_bb_range (r, name, bb))
1199 if (!range_from_dom (r, name, bb, mode))
1200 range_of_def (r, name);
1201}
1202
1203// Get the range of NAME as it occurs on exit from block BB. Use MODE for
1204// lookups.
1205
1206void
1207ranger_cache::exit_range (vrange &r, tree name, basic_block bb,
1208 enum rfd_mode mode)
1209{
1210 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1211 {
1212 gimple_range_global (v&: r, name);
1213 return;
1214 }
1215
1216 gimple *s = SSA_NAME_DEF_STMT (name);
1217 basic_block def_bb = gimple_bb (g: s);
1218 if (def_bb == bb)
1219 range_of_def (r, name, bb);
1220 else
1221 entry_range (r, name, bb, mode);
1222}
1223
1224// Get the range of NAME on edge E using MODE, return the result in R.
1225// Always returns a range and true.
1226
1227bool
1228ranger_cache::edge_range (vrange &r, edge e, tree name, enum rfd_mode mode)
1229{
1230 exit_range (r, name, bb: e->src, mode);
1231 // If this is not an abnormal edge, check for inferred ranges on exit.
1232 if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
1233 infer_oracle ().maybe_adjust_range (r, name, e->src);
1234 value_range er (TREE_TYPE (name));
1235 if (gori ().edge_range_p (er, e, name, *this))
1236 r.intersect (er);
1237 return true;
1238}
1239
1240
1241
1242// Implement range_of_expr.
1243
1244bool
1245ranger_cache::range_of_expr (vrange &r, tree name, gimple *stmt)
1246{
1247 if (!gimple_range_ssa_p (exp: name))
1248 {
1249 get_tree_range (v&: r, expr: name, stmt);
1250 return true;
1251 }
1252
1253 basic_block bb = gimple_bb (g: stmt);
1254 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1255 basic_block def_bb = gimple_bb (g: def_stmt);
1256
1257 if (bb == def_bb)
1258 range_of_def (r, name, bb);
1259 else
1260 entry_range (r, name, bb, mode: RFD_NONE);
1261 return true;
1262}
1263
1264
1265// Implement range_on_edge. Always return the best available range using
1266// the current cache values.
1267
1268bool
1269ranger_cache::range_on_edge (vrange &r, edge e, tree expr)
1270{
1271 if (gimple_range_ssa_p (exp: expr))
1272 return edge_range (r, e, name: expr, mode: RFD_NONE);
1273 return get_tree_range (v&: r, expr, NULL);
1274}
1275
1276// Return a static range for NAME on entry to basic block BB in R. If
1277// calc is true, fill any cache entries required between BB and the
1278// def block for NAME. Otherwise, return false if the cache is empty.
1279
1280bool
1281ranger_cache::block_range (vrange &r, basic_block bb, tree name, bool calc)
1282{
1283 gcc_checking_assert (gimple_range_ssa_p (name));
1284
1285 // If there are no range calculations anywhere in the IL, global range
1286 // applies everywhere, so don't bother caching it.
1287 if (!gori ().has_edge_range_p (name))
1288 return false;
1289
1290 if (calc)
1291 {
1292 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1293 basic_block def_bb = NULL;
1294 if (def_stmt)
1295 def_bb = gimple_bb (g: def_stmt);
1296 if (!def_bb)
1297 {
1298 // If we get to the entry block, this better be a default def
1299 // or range_on_entry was called for a block not dominated by
1300 // the def. But it could be also SSA_NAME defined by a statement
1301 // not yet in the IL (such as queued edge insertion), in that case
1302 // just punt.
1303 if (!SSA_NAME_IS_DEFAULT_DEF (name))
1304 return false;
1305 def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1306 }
1307
1308 // There is no range on entry for the definition block.
1309 if (def_bb == bb)
1310 return false;
1311
1312 // Otherwise, go figure out what is known in predecessor blocks.
1313 fill_block_cache (name, bb, def_bb);
1314 gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
1315 }
1316 return m_on_entry.get_bb_range (r, name, bb);
1317}
1318
1319// If there is anything in the propagation update_list, continue
1320// processing NAME until the list of blocks is empty.
1321
1322void
1323ranger_cache::propagate_cache (tree name)
1324{
1325 basic_block bb;
1326 edge_iterator ei;
1327 edge e;
1328 tree type = TREE_TYPE (name);
1329 value_range new_range (type);
1330 value_range current_range (type);
1331 value_range e_range (type);
1332
1333 // Process each block by seeing if its calculated range on entry is
1334 // the same as its cached value. If there is a difference, update
1335 // the cache to reflect the new value, and check to see if any
1336 // successors have cache entries which may need to be checked for
1337 // updates.
1338
1339 while (!m_update->empty_p ())
1340 {
1341 bb = m_update->pop ();
1342 gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
1343 m_on_entry.get_bb_range (r&: current_range, name, bb);
1344
1345 if (DEBUG_RANGE_CACHE)
1346 {
1347 fprintf (stream: dump_file, format: "FWD visiting block %d for ", bb->index);
1348 print_generic_expr (dump_file, name, TDF_SLIM);
1349 fprintf (stream: dump_file, format: " starting range : ");
1350 current_range.dump (dump_file);
1351 fprintf (stream: dump_file, format: "\n");
1352 }
1353
1354 // Calculate the "new" range on entry by unioning the pred edges.
1355 new_range.set_undefined ();
1356 FOR_EACH_EDGE (e, ei, bb->preds)
1357 {
1358 edge_range (r&: e_range, e, name, mode: RFD_READ_ONLY);
1359 if (DEBUG_RANGE_CACHE)
1360 {
1361 fprintf (stream: dump_file, format: " edge %d->%d :", e->src->index, bb->index);
1362 e_range.dump (dump_file);
1363 fprintf (stream: dump_file, format: "\n");
1364 }
1365 new_range.union_ (r: e_range);
1366 if (new_range.varying_p ())
1367 break;
1368 }
1369
1370 // If the range on entry has changed, update it.
1371 if (new_range != current_range)
1372 {
1373 bool ok_p = m_on_entry.set_bb_range (name, bb, r: new_range);
1374 // If the cache couldn't set the value, mark it as failed.
1375 if (!ok_p)
1376 m_update->propagation_failed (bb);
1377 if (DEBUG_RANGE_CACHE)
1378 {
1379 if (!ok_p)
1380 {
1381 fprintf (stream: dump_file, format: " Cache failure to store value:");
1382 print_generic_expr (dump_file, name, TDF_SLIM);
1383 fprintf (stream: dump_file, format: " ");
1384 }
1385 else
1386 {
1387 fprintf (stream: dump_file, format: " Updating range to ");
1388 new_range.dump (dump_file);
1389 }
1390 fprintf (stream: dump_file, format: "\n Updating blocks :");
1391 }
1392 // Mark each successor that has a range to re-check its range
1393 FOR_EACH_EDGE (e, ei, bb->succs)
1394 if (m_on_entry.bb_range_p (name, bb: e->dest))
1395 {
1396 if (DEBUG_RANGE_CACHE)
1397 fprintf (stream: dump_file, format: " bb%d",e->dest->index);
1398 m_update->add (bb: e->dest);
1399 }
1400 if (DEBUG_RANGE_CACHE)
1401 fprintf (stream: dump_file, format: "\n");
1402 }
1403 }
1404 if (DEBUG_RANGE_CACHE)
1405 {
1406 fprintf (stream: dump_file, format: "DONE visiting blocks for ");
1407 print_generic_expr (dump_file, name, TDF_SLIM);
1408 fprintf (stream: dump_file, format: "\n");
1409 }
1410 m_update->clear_failures ();
1411}
1412
1413// Check to see if an update to the value for NAME in BB has any effect
1414// on values already in the on-entry cache for successor blocks.
1415// If it does, update them. Don't visit any blocks which don't have a cache
1416// entry.
1417
1418void
1419ranger_cache::propagate_updated_value (tree name, basic_block bb)
1420{
1421 edge e;
1422 edge_iterator ei;
1423
1424 // The update work list should be empty at this point.
1425 gcc_checking_assert (m_update->empty_p ());
1426 gcc_checking_assert (bb);
1427
1428 if (DEBUG_RANGE_CACHE)
1429 {
1430 fprintf (stream: dump_file, format: " UPDATE cache for ");
1431 print_generic_expr (dump_file, name, TDF_SLIM);
1432 fprintf (stream: dump_file, format: " in BB %d : successors : ", bb->index);
1433 }
1434 FOR_EACH_EDGE (e, ei, bb->succs)
1435 {
1436 // Only update active cache entries.
1437 if (m_on_entry.bb_range_p (name, bb: e->dest))
1438 {
1439 m_update->add (bb: e->dest);
1440 if (DEBUG_RANGE_CACHE)
1441 fprintf (stream: dump_file, format: " UPDATE: bb%d", e->dest->index);
1442 }
1443 }
1444 if (!m_update->empty_p ())
1445 {
1446 if (DEBUG_RANGE_CACHE)
1447 fprintf (stream: dump_file, format: "\n");
1448 propagate_cache (name);
1449 }
1450 else
1451 {
1452 if (DEBUG_RANGE_CACHE)
1453 fprintf (stream: dump_file, format: " : No updates!\n");
1454 }
1455}
1456
1457// Make sure that the range-on-entry cache for NAME is set for block BB.
1458// Work back through the CFG to DEF_BB ensuring the range is calculated
1459// on the block/edges leading back to that point.
1460
1461void
1462ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
1463{
1464 edge_iterator ei;
1465 edge e;
1466 tree type = TREE_TYPE (name);
1467 value_range block_result (type);
1468 value_range undefined (type);
1469
1470 // At this point we shouldn't be looking at the def, entry block.
1471 gcc_checking_assert (bb != def_bb && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
1472 unsigned start_length = m_workback.length ();
1473
1474 // If the block cache is set, then we've already visited this block.
1475 if (m_on_entry.bb_range_p (name, bb))
1476 return;
1477
1478 if (DEBUG_RANGE_CACHE)
1479 {
1480 fprintf (stream: dump_file, format: "\n");
1481 print_generic_expr (dump_file, name, TDF_SLIM);
1482 fprintf (stream: dump_file, format: " : ");
1483 }
1484
1485 // Check if a dominators can supply the range.
1486 if (range_from_dom (r&: block_result, name, bb, RFD_FILL))
1487 {
1488 if (DEBUG_RANGE_CACHE)
1489 {
1490 fprintf (stream: dump_file, format: "Filled from dominator! : ");
1491 block_result.dump (dump_file);
1492 fprintf (stream: dump_file, format: "\n");
1493 }
1494 // See if any equivalences can refine it.
1495 // PR 109462, like 108139 below, a one way equivalence introduced
1496 // by a PHI node can also be through the definition side. Disallow it.
1497 tree equiv_name;
1498 relation_kind rel;
1499 int prec = TYPE_PRECISION (type);
1500 // If there are too many basic blocks, do not attempt to process
1501 // equivalencies.
1502 if (last_basic_block_for_fn (cfun) > param_vrp_sparse_threshold)
1503 {
1504 m_on_entry.set_bb_range (name, bb, r: block_result);
1505 gcc_checking_assert (m_workback.length () == start_length);
1506 return;
1507 }
1508 FOR_EACH_PARTIAL_AND_FULL_EQUIV (m_relation, bb, name, equiv_name, rel)
1509 {
1510 basic_block equiv_bb = gimple_bb (SSA_NAME_DEF_STMT (equiv_name));
1511
1512 // Ignore partial equivs that are smaller than this object.
1513 if (rel != VREL_EQ && prec > pe_to_bits (t: rel))
1514 continue;
1515
1516 // Check if the equiv has any ranges calculated.
1517 if (!gori ().has_edge_range_p (equiv_name))
1518 continue;
1519
1520 // Check if the equiv definition dominates this block
1521 if (equiv_bb == bb ||
1522 (equiv_bb && !dominated_by_p (CDI_DOMINATORS, bb, equiv_bb)))
1523 continue;
1524
1525 if (DEBUG_RANGE_CACHE)
1526 {
1527 if (rel == VREL_EQ)
1528 fprintf (stream: dump_file, format: "Checking Equivalence (");
1529 else
1530 fprintf (stream: dump_file, format: "Checking Partial equiv (");
1531 print_relation (f: dump_file, rel);
1532 fprintf (stream: dump_file, format: ") ");
1533 print_generic_expr (dump_file, equiv_name, TDF_SLIM);
1534 fprintf (stream: dump_file, format: "\n");
1535 }
1536 value_range equiv_range (TREE_TYPE (equiv_name));
1537 if (range_from_dom (r&: equiv_range, name: equiv_name, bb, RFD_READ_ONLY))
1538 {
1539 if (rel != VREL_EQ)
1540 range_cast (r&: equiv_range, type);
1541 else
1542 adjust_equivalence_range (range&: equiv_range);
1543
1544 if (block_result.intersect (r: equiv_range))
1545 {
1546 if (DEBUG_RANGE_CACHE)
1547 {
1548 if (rel == VREL_EQ)
1549 fprintf (stream: dump_file, format: "Equivalence update! : ");
1550 else
1551 fprintf (stream: dump_file, format: "Partial equiv update! : ");
1552 print_generic_expr (dump_file, equiv_name, TDF_SLIM);
1553 fprintf (stream: dump_file, format: " has range : ");
1554 equiv_range.dump (dump_file);
1555 fprintf (stream: dump_file, format: " refining range to :");
1556 block_result.dump (dump_file);
1557 fprintf (stream: dump_file, format: "\n");
1558 }
1559 }
1560 }
1561 }
1562
1563 m_on_entry.set_bb_range (name, bb, r: block_result);
1564 gcc_checking_assert (m_workback.length () == start_length);
1565 return;
1566 }
1567
1568 // Visit each block back to the DEF. Initialize each one to UNDEFINED.
1569 // m_visited at the end will contain all the blocks that we needed to set
1570 // the range_on_entry cache for.
1571 m_workback.safe_push (obj: bb);
1572 undefined.set_undefined ();
1573 m_on_entry.set_bb_range (name, bb, r: undefined);
1574 gcc_checking_assert (m_update->empty_p ());
1575
1576 while (m_workback.length () > start_length)
1577 {
1578 basic_block node = m_workback.pop ();
1579 if (DEBUG_RANGE_CACHE)
1580 {
1581 fprintf (stream: dump_file, format: "BACK visiting block %d for ", node->index);
1582 print_generic_expr (dump_file, name, TDF_SLIM);
1583 fprintf (stream: dump_file, format: "\n");
1584 }
1585
1586 FOR_EACH_EDGE (e, ei, node->preds)
1587 {
1588 basic_block pred = e->src;
1589 value_range r (TREE_TYPE (name));
1590
1591 if (DEBUG_RANGE_CACHE)
1592 fprintf (stream: dump_file, format: " %d->%d ",e->src->index, e->dest->index);
1593
1594 // If the pred block is the def block add this BB to update list.
1595 if (pred == def_bb)
1596 {
1597 m_update->add (bb: node);
1598 continue;
1599 }
1600
1601 // If the pred is entry but NOT def, then it is used before
1602 // defined, it'll get set to [] and no need to update it.
1603 if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1604 {
1605 if (DEBUG_RANGE_CACHE)
1606 fprintf (stream: dump_file, format: "entry: bail.");
1607 continue;
1608 }
1609
1610 // Regardless of whether we have visited pred or not, if the
1611 // pred has inferred ranges, revisit this block.
1612 // Don't search the DOM tree.
1613 if (infer_oracle ().has_range_p (pred, name))
1614 {
1615 if (DEBUG_RANGE_CACHE)
1616 fprintf (stream: dump_file, format: "Inferred range: update ");
1617 m_update->add (bb: node);
1618 }
1619
1620 // If the pred block already has a range, or if it can contribute
1621 // something new. Ie, the edge generates a range of some sort.
1622 if (m_on_entry.get_bb_range (r, name, bb: pred))
1623 {
1624 if (DEBUG_RANGE_CACHE)
1625 {
1626 fprintf (stream: dump_file, format: "has cache, ");
1627 r.dump (dump_file);
1628 fprintf (stream: dump_file, format: ", ");
1629 }
1630 if (!r.undefined_p () || gori ().has_edge_range_p (name, e))
1631 {
1632 m_update->add (bb: node);
1633 if (DEBUG_RANGE_CACHE)
1634 fprintf (stream: dump_file, format: "update. ");
1635 }
1636 continue;
1637 }
1638
1639 if (DEBUG_RANGE_CACHE)
1640 fprintf (stream: dump_file, format: "pushing undefined pred block.\n");
1641 // If the pred hasn't been visited (has no range), add it to
1642 // the list.
1643 gcc_checking_assert (!m_on_entry.bb_range_p (name, pred));
1644 m_on_entry.set_bb_range (name, bb: pred, r: undefined);
1645 m_workback.safe_push (obj: pred);
1646 }
1647 }
1648
1649 if (DEBUG_RANGE_CACHE)
1650 fprintf (stream: dump_file, format: "\n");
1651
1652 // Now fill in the marked blocks with values.
1653 propagate_cache (name);
1654 if (DEBUG_RANGE_CACHE)
1655 fprintf (stream: dump_file, format: " Propagation update done.\n");
1656}
1657
1658// Resolve the range of BB if the dominators range is R by calculating incoming
1659// edges to this block. All lead back to the dominator so should be cheap.
1660// The range for BB is set and returned in R.
1661
1662void
1663ranger_cache::resolve_dom (vrange &r, tree name, basic_block bb)
1664{
1665 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1666 basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1667
1668 // if it doesn't already have a value, store the incoming range.
1669 if (!m_on_entry.bb_range_p (name, bb: dom_bb) && def_bb != dom_bb)
1670 {
1671 // If the range can't be store, don't try to accumulate
1672 // the range in PREV_BB due to excessive recalculations.
1673 if (!m_on_entry.set_bb_range (name, bb: dom_bb, r))
1674 return;
1675 }
1676 // With the dominator set, we should be able to cheaply query
1677 // each incoming edge now and accumulate the results.
1678 r.set_undefined ();
1679 edge e;
1680 edge_iterator ei;
1681 value_range er (TREE_TYPE (name));
1682 FOR_EACH_EDGE (e, ei, bb->preds)
1683 {
1684 // If the predecessor is dominated by this block, then there is a back
1685 // edge, and won't provide anything useful. We'll actually end up with
1686 // VARYING as we will not resolve this node.
1687 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1688 continue;
1689 edge_range (r&: er, e, name, mode: RFD_READ_ONLY);
1690 r.union_ (er);
1691 }
1692 // Set the cache in PREV_BB so it is not calculated again.
1693 m_on_entry.set_bb_range (name, bb, r);
1694}
1695
1696// Get the range of NAME from dominators of BB and return it in R. Search the
1697// dominator tree based on MODE.
1698
1699bool
1700ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
1701 enum rfd_mode mode)
1702{
1703 if (mode == RFD_NONE || !dom_info_available_p (CDI_DOMINATORS))
1704 return false;
1705
1706 // Search back to the definition block or entry block.
1707 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1708 if (def_bb == NULL)
1709 def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1710
1711 basic_block bb;
1712 basic_block prev_bb = start_bb;
1713
1714 // Track any inferred ranges seen.
1715 value_range infer (TREE_TYPE (name));
1716 infer.set_varying (TREE_TYPE (name));
1717
1718 // Range on entry to the DEF block should not be queried.
1719 gcc_checking_assert (start_bb != def_bb);
1720 unsigned start_limit = m_workback.length ();
1721
1722 // Default value is global range.
1723 get_global_range (r, name);
1724
1725 // The dominator of EXIT_BLOCK doesn't seem to be set, so at least handle
1726 // the common single exit cases.
1727 if (start_bb == EXIT_BLOCK_PTR_FOR_FN (cfun) && single_pred_p (bb: start_bb))
1728 bb = single_pred_edge (bb: start_bb)->src;
1729 else
1730 bb = get_immediate_dominator (CDI_DOMINATORS, start_bb);
1731
1732 // Search until a value is found, pushing blocks which may need calculating.
1733 for ( ; bb; prev_bb = bb, bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1734 {
1735 // Accumulate any block exit inferred ranges.
1736 infer_oracle ().maybe_adjust_range (infer, name, bb);
1737
1738 // This block has an outgoing range.
1739 if (gori ().has_edge_range_p (name, bb))
1740 m_workback.safe_push (obj: prev_bb);
1741 else
1742 {
1743 // Normally join blocks don't carry any new range information on
1744 // incoming edges. If the first incoming edge to this block does
1745 // generate a range, calculate the ranges if all incoming edges
1746 // are also dominated by the dominator. (Avoids backedges which
1747 // will break the rule of moving only upward in the dominator tree).
1748 // If the first pred does not generate a range, then we will be
1749 // using the dominator range anyway, so that's all the check needed.
1750 if (EDGE_COUNT (prev_bb->preds) > 1
1751 && gori ().has_edge_range_p (name, EDGE_PRED (prev_bb, 0)->src))
1752 {
1753 edge e;
1754 edge_iterator ei;
1755 bool all_dom = true;
1756 FOR_EACH_EDGE (e, ei, prev_bb->preds)
1757 if (e->src != bb
1758 && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
1759 {
1760 all_dom = false;
1761 break;
1762 }
1763 if (all_dom)
1764 m_workback.safe_push (obj: prev_bb);
1765 }
1766 }
1767
1768 if (def_bb == bb)
1769 break;
1770
1771 if (m_on_entry.get_bb_range (r, name, bb))
1772 break;
1773 }
1774
1775 if (DEBUG_RANGE_CACHE)
1776 {
1777 fprintf (stream: dump_file, format: "CACHE: BB %d DOM query for ", start_bb->index);
1778 print_generic_expr (dump_file, name, TDF_SLIM);
1779 fprintf (stream: dump_file, format: ", found ");
1780 r.dump (dump_file);
1781 if (bb)
1782 fprintf (stream: dump_file, format: " at BB%d\n", bb->index);
1783 else
1784 fprintf (stream: dump_file, format: " at function top\n");
1785 }
1786
1787 // Now process any blocks wit incoming edges that nay have adjustments.
1788 while (m_workback.length () > start_limit)
1789 {
1790 value_range er (TREE_TYPE (name));
1791 prev_bb = m_workback.pop ();
1792 if (!single_pred_p (bb: prev_bb))
1793 {
1794 // Non single pred means we need to cache a value in the dominator
1795 // so we can cheaply calculate incoming edges to this block, and
1796 // then store the resulting value. If processing mode is not
1797 // RFD_FILL, then the cache cant be stored to, so don't try.
1798 // Otherwise this becomes a quadratic timed calculation.
1799 if (mode == RFD_FILL)
1800 resolve_dom (r, name, bb: prev_bb);
1801 continue;
1802 }
1803
1804 edge e = single_pred_edge (bb: prev_bb);
1805 bb = e->src;
1806 if (gori ().edge_range_p (er, e, name, *this))
1807 {
1808 r.intersect (er);
1809 // If this is a normal edge, apply any inferred ranges.
1810 if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
1811 infer_oracle ().maybe_adjust_range (r, name, bb);
1812
1813 if (DEBUG_RANGE_CACHE)
1814 {
1815 fprintf (stream: dump_file, format: "CACHE: Adjusted edge range for %d->%d : ",
1816 bb->index, prev_bb->index);
1817 r.dump (dump_file);
1818 fprintf (stream: dump_file, format: "\n");
1819 }
1820 }
1821 }
1822
1823 // Apply non-null if appropriate.
1824 if (!has_abnormal_call_or_eh_pred_edge_p (bb: start_bb))
1825 r.intersect (infer);
1826
1827 if (DEBUG_RANGE_CACHE)
1828 {
1829 fprintf (stream: dump_file, format: "CACHE: Range for DOM returns : ");
1830 r.dump (dump_file);
1831 fprintf (stream: dump_file, format: "\n");
1832 }
1833 return true;
1834}
1835
1836// This routine will register an inferred value in block BB, and possibly
1837// update the on-entry cache if appropriate.
1838
1839void
1840ranger_cache::register_inferred_value (const vrange &ir, tree name,
1841 basic_block bb)
1842{
1843 value_range r (TREE_TYPE (name));
1844 if (!m_on_entry.get_bb_range (r, name, bb))
1845 exit_range (r, name, bb, mode: RFD_READ_ONLY);
1846 if (r.intersect (r: ir))
1847 {
1848 m_on_entry.set_bb_range (name, bb, r);
1849 // If this range was invariant before, remove invariant.
1850 if (!gori ().has_edge_range_p (name))
1851 gori_ssa ()->set_range_invariant (name, invariant: false);
1852 }
1853}
1854
1855// This routine is used during a block walk to adjust any inferred ranges
1856// of operands on stmt S.
1857
1858void
1859ranger_cache::apply_inferred_ranges (gimple *s)
1860{
1861 bool update = true;
1862
1863 basic_block bb = gimple_bb (g: s);
1864 gimple_infer_range infer(s, this);
1865 if (infer.num () == 0)
1866 return;
1867
1868 // Do not update the on-entry cache for block ending stmts.
1869 if (stmt_ends_bb_p (s))
1870 {
1871 edge_iterator ei;
1872 edge e;
1873 FOR_EACH_EDGE (e, ei, gimple_bb (s)->succs)
1874 if (!(e->flags & (EDGE_ABNORMAL|EDGE_EH)))
1875 break;
1876 if (e == NULL)
1877 update = false;
1878 }
1879
1880 infer_oracle ().add_ranges (s, infer);
1881 if (update)
1882 for (unsigned x = 0; x < infer.num (); x++)
1883 register_inferred_value (ir: infer.range (index: x), name: infer.name (index: x), bb);
1884}
1885

source code of gcc/gimple-range-cache.cc