1/* Gimple ranger SSA cache implementation.
2 Copyright (C) 2017-2024 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 int_range<2> nonzero;
278 nonzero.set_nonzero (t);
279 m_range[1] = m_range_allocator->clone (r: nonzero);
280 int_range<2> 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// Return true if NAME has an active range in the cache.
687
688bool
689ssa_lazy_cache::has_range (tree name) const
690{
691 return bitmap_bit_p (active_p, SSA_NAME_VERSION (name));
692}
693
694// Set range of NAME to R in a lazy cache. Return FALSE if it did not already
695// have a range.
696
697bool
698ssa_lazy_cache::set_range (tree name, const vrange &r)
699{
700 unsigned v = SSA_NAME_VERSION (name);
701 if (!bitmap_set_bit (active_p, v))
702 {
703 // There is already an entry, simply set it.
704 gcc_checking_assert (v < m_tab.length ());
705 return ssa_cache::set_range (name, r);
706 }
707 if (v >= m_tab.length ())
708 m_tab.safe_grow (num_ssa_names + 1);
709 m_tab[v] = m_range_allocator->clone (r);
710 return false;
711}
712
713// If NAME has a range, intersect it with R, otherwise set it to R.
714// Return TRUE if the range is new or changes.
715
716bool
717ssa_lazy_cache::merge_range (tree name, const vrange &r)
718{
719 unsigned v = SSA_NAME_VERSION (name);
720 if (!bitmap_set_bit (active_p, v))
721 {
722 // There is already an entry, simply merge it.
723 gcc_checking_assert (v < m_tab.length ());
724 return ssa_cache::merge_range (name, r);
725 }
726 if (v >= m_tab.length ())
727 m_tab.safe_grow (num_ssa_names + 1);
728 m_tab[v] = m_range_allocator->clone (r);
729 return true;
730}
731
732// Return TRUE if NAME has a range, and return it in R.
733
734bool
735ssa_lazy_cache::get_range (vrange &r, tree name) const
736{
737 if (!bitmap_bit_p (active_p, SSA_NAME_VERSION (name)))
738 return false;
739 return ssa_cache::get_range (r, name);
740}
741
742// Remove NAME from the active range list.
743
744void
745ssa_lazy_cache::clear_range (tree name)
746{
747 bitmap_clear_bit (active_p, SSA_NAME_VERSION (name));
748}
749
750// Remove all ranges from the active range list.
751
752void
753ssa_lazy_cache::clear ()
754{
755 bitmap_clear (active_p);
756}
757
758// --------------------------------------------------------------------------
759
760
761// This class will manage the timestamps for each ssa_name.
762// When a value is calculated, the timestamp is set to the current time.
763// Current time is then incremented. Any dependencies will already have
764// been calculated, and will thus have older timestamps.
765// If one of those values is ever calculated again, it will get a newer
766// timestamp, and the "current_p" check will fail.
767
768class temporal_cache
769{
770public:
771 temporal_cache ();
772 ~temporal_cache ();
773 bool current_p (tree name, tree dep1, tree dep2) const;
774 void set_timestamp (tree name);
775 void set_always_current (tree name, bool value);
776 bool always_current_p (tree name) const;
777private:
778 int temporal_value (unsigned ssa) const;
779 int m_current_time;
780 vec <int> m_timestamp;
781};
782
783inline
784temporal_cache::temporal_cache ()
785{
786 m_current_time = 1;
787 m_timestamp.create (nelems: 0);
788 m_timestamp.safe_grow_cleared (num_ssa_names);
789}
790
791inline
792temporal_cache::~temporal_cache ()
793{
794 m_timestamp.release ();
795}
796
797// Return the timestamp value for SSA, or 0 if there isn't one.
798
799inline int
800temporal_cache::temporal_value (unsigned ssa) const
801{
802 if (ssa >= m_timestamp.length ())
803 return 0;
804 return abs (x: m_timestamp[ssa]);
805}
806
807// Return TRUE if the timestamp for NAME is newer than any of its dependents.
808// Up to 2 dependencies can be checked.
809
810bool
811temporal_cache::current_p (tree name, tree dep1, tree dep2) const
812{
813 if (always_current_p (name))
814 return true;
815
816 // Any non-registered dependencies will have a value of 0 and thus be older.
817 // Return true if time is newer than either dependent.
818 int ts = temporal_value (SSA_NAME_VERSION (name));
819 if (dep1 && ts < temporal_value (SSA_NAME_VERSION (dep1)))
820 return false;
821 if (dep2 && ts < temporal_value (SSA_NAME_VERSION (dep2)))
822 return false;
823
824 return true;
825}
826
827// This increments the global timer and sets the timestamp for NAME.
828
829inline void
830temporal_cache::set_timestamp (tree name)
831{
832 unsigned v = SSA_NAME_VERSION (name);
833 if (v >= m_timestamp.length ())
834 m_timestamp.safe_grow_cleared (num_ssa_names + 20);
835 m_timestamp[v] = ++m_current_time;
836}
837
838// Set the timestamp to 0, marking it as "always up to date".
839
840inline void
841temporal_cache::set_always_current (tree name, bool value)
842{
843 unsigned v = SSA_NAME_VERSION (name);
844 if (v >= m_timestamp.length ())
845 m_timestamp.safe_grow_cleared (num_ssa_names + 20);
846
847 int ts = abs (x: m_timestamp[v]);
848 // If this does not have a timestamp, create one.
849 if (ts == 0)
850 ts = ++m_current_time;
851 m_timestamp[v] = value ? -ts : ts;
852}
853
854// Return true if NAME is always current.
855
856inline bool
857temporal_cache::always_current_p (tree name) const
858{
859 unsigned v = SSA_NAME_VERSION (name);
860 if (v >= m_timestamp.length ())
861 return false;
862 return m_timestamp[v] <= 0;
863}
864
865// --------------------------------------------------------------------------
866
867// This class provides an abstraction of a list of blocks to be updated
868// by the cache. It is currently a stack but could be changed. It also
869// maintains a list of blocks which have failed propagation, and does not
870// enter any of those blocks into the list.
871
872// A vector over the BBs is maintained, and an entry of 0 means it is not in
873// a list. Otherwise, the entry is the next block in the list. -1 terminates
874// the list. m_head points to the top of the list, -1 if the list is empty.
875
876class update_list
877{
878public:
879 update_list ();
880 ~update_list ();
881 void add (basic_block bb);
882 basic_block pop ();
883 inline bool empty_p () { return m_update_head == -1; }
884 inline void clear_failures () { bitmap_clear (m_propfail); }
885 inline void propagation_failed (basic_block bb)
886 { bitmap_set_bit (m_propfail, bb->index); }
887private:
888 vec<int> m_update_list;
889 int m_update_head;
890 bitmap m_propfail;
891};
892
893// Create an update list.
894
895update_list::update_list ()
896{
897 m_update_list.create (nelems: 0);
898 m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun) + 64);
899 m_update_head = -1;
900 m_propfail = BITMAP_ALLOC (NULL);
901}
902
903// Destroy an update list.
904
905update_list::~update_list ()
906{
907 m_update_list.release ();
908 BITMAP_FREE (m_propfail);
909}
910
911// Add BB to the list of blocks to update, unless it's already in the list.
912
913void
914update_list::add (basic_block bb)
915{
916 int i = bb->index;
917 // If propagation has failed for BB, or its already in the list, don't
918 // add it again.
919 if ((unsigned)i >= m_update_list.length ())
920 m_update_list.safe_grow_cleared (len: i + 64);
921 if (!m_update_list[i] && !bitmap_bit_p (m_propfail, i))
922 {
923 if (empty_p ())
924 {
925 m_update_head = i;
926 m_update_list[i] = -1;
927 }
928 else
929 {
930 gcc_checking_assert (m_update_head > 0);
931 m_update_list[i] = m_update_head;
932 m_update_head = i;
933 }
934 }
935}
936
937// Remove a block from the list.
938
939basic_block
940update_list::pop ()
941{
942 gcc_checking_assert (!empty_p ());
943 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, m_update_head);
944 int pop = m_update_head;
945 m_update_head = m_update_list[pop];
946 m_update_list[pop] = 0;
947 return bb;
948}
949
950// --------------------------------------------------------------------------
951
952ranger_cache::ranger_cache (int not_executable_flag, bool use_imm_uses)
953 : m_gori (not_executable_flag),
954 m_exit (use_imm_uses)
955{
956 m_workback.create (nelems: 0);
957 m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun));
958 m_workback.truncate (size: 0);
959 m_temporal = new temporal_cache;
960 // If DOM info is available, spawn an oracle as well.
961 if (dom_info_available_p (CDI_DOMINATORS))
962 m_oracle = new dom_oracle ();
963 else
964 m_oracle = NULL;
965
966 unsigned x, lim = last_basic_block_for_fn (cfun);
967 // Calculate outgoing range info upfront. This will fully populate the
968 // m_maybe_variant bitmap which will help eliminate processing of names
969 // which never have their ranges adjusted.
970 for (x = 0; x < lim ; x++)
971 {
972 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, x);
973 if (bb)
974 m_gori.exports (bb);
975 }
976 m_update = new update_list ();
977}
978
979ranger_cache::~ranger_cache ()
980{
981 delete m_update;
982 if (m_oracle)
983 delete m_oracle;
984 delete m_temporal;
985 m_workback.release ();
986}
987
988// Dump the global caches to file F. if GORI_DUMP is true, dump the
989// gori map as well.
990
991void
992ranger_cache::dump (FILE *f)
993{
994 fprintf (stream: f, format: "Non-varying global ranges:\n");
995 fprintf (stream: f, format: "=========================:\n");
996 m_globals.dump (f);
997 fprintf (stream: f, format: "\n");
998}
999
1000// Dump the caches for basic block BB to file F.
1001
1002void
1003ranger_cache::dump_bb (FILE *f, basic_block bb)
1004{
1005 m_gori.gori_map::dump (f, bb, verbose: false);
1006 m_on_entry.dump (f, bb);
1007 if (m_oracle)
1008 m_oracle->dump (f, bb);
1009}
1010
1011// Get the global range for NAME, and return in R. Return false if the
1012// global range is not set, and return the legacy global value in R.
1013
1014bool
1015ranger_cache::get_global_range (vrange &r, tree name) const
1016{
1017 if (m_globals.get_range (r, name))
1018 return true;
1019 gimple_range_global (v&: r, name);
1020 return false;
1021}
1022
1023// Get the global range for NAME, and return in R. Return false if the
1024// global range is not set, and R will contain the legacy global value.
1025// CURRENT_P is set to true if the value was in cache and not stale.
1026// Otherwise, set CURRENT_P to false and mark as it always current.
1027// If the global cache did not have a value, initialize it as well.
1028// After this call, the global cache will have a value.
1029
1030bool
1031ranger_cache::get_global_range (vrange &r, tree name, bool &current_p)
1032{
1033 bool had_global = get_global_range (r, name);
1034
1035 // If there was a global value, set current flag, otherwise set a value.
1036 current_p = false;
1037 if (had_global)
1038 current_p = r.singleton_p ()
1039 || m_temporal->current_p (name, dep1: m_gori.depend1 (name),
1040 dep2: m_gori.depend2 (name));
1041 else
1042 {
1043 // If no global value has been set and value is VARYING, fold the stmt
1044 // using just global ranges to get a better initial value.
1045 // After inlining we tend to decide some things are constant, so
1046 // so not do this evaluation after inlining.
1047 if (r.varying_p () && !cfun->after_inlining)
1048 {
1049 gimple *s = SSA_NAME_DEF_STMT (name);
1050 if (gimple_get_lhs (s) == name)
1051 {
1052 if (!fold_range (r, s, q: get_global_range_query ()))
1053 gimple_range_global (v&: r, name);
1054 }
1055 }
1056 m_globals.set_range (name, r);
1057 }
1058
1059 // If the existing value was not current, mark it as always current.
1060 if (!current_p)
1061 m_temporal->set_always_current (name, value: true);
1062 return had_global;
1063}
1064
1065// Set the global range of NAME to R and give it a timestamp.
1066
1067void
1068ranger_cache::set_global_range (tree name, const vrange &r, bool changed)
1069{
1070 // Setting a range always clears the always_current flag.
1071 m_temporal->set_always_current (name, value: false);
1072 if (!changed)
1073 {
1074 // If there are dependencies, make sure this is not out of date.
1075 if (!m_temporal->current_p (name, dep1: m_gori.depend1 (name),
1076 dep2: m_gori.depend2 (name)))
1077 m_temporal->set_timestamp (name);
1078 return;
1079 }
1080 if (m_globals.set_range (name, r))
1081 {
1082 // If there was already a range set, propagate the new value.
1083 basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1084 if (!bb)
1085 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1086
1087 if (DEBUG_RANGE_CACHE)
1088 fprintf (stream: dump_file, format: " GLOBAL :");
1089
1090 propagate_updated_value (name, bb);
1091 }
1092 // Constants no longer need to tracked. Any further refinement has to be
1093 // undefined. Propagation works better with constants. PR 100512.
1094 // Pointers which resolve to non-zero also do not need
1095 // tracking in the cache as they will never change. See PR 98866.
1096 // Timestamp must always be updated, or dependent calculations may
1097 // not include this latest value. PR 100774.
1098
1099 if (r.singleton_p ()
1100 || (POINTER_TYPE_P (TREE_TYPE (name)) && r.nonzero_p ()))
1101 m_gori.set_range_invariant (name);
1102 m_temporal->set_timestamp (name);
1103}
1104
1105// Provide lookup for the gori-computes class to access the best known range
1106// of an ssa_name in any given basic block. Note, this does no additional
1107// lookups, just accesses the data that is already known.
1108
1109// Get the range of NAME when the def occurs in block BB. If BB is NULL
1110// get the best global value available.
1111
1112void
1113ranger_cache::range_of_def (vrange &r, tree name, basic_block bb)
1114{
1115 gcc_checking_assert (gimple_range_ssa_p (name));
1116 gcc_checking_assert (!bb || bb == gimple_bb (SSA_NAME_DEF_STMT (name)));
1117
1118 // Pick up the best global range available.
1119 if (!m_globals.get_range (r, name))
1120 {
1121 // If that fails, try to calculate the range using just global values.
1122 gimple *s = SSA_NAME_DEF_STMT (name);
1123 if (gimple_get_lhs (s) == name)
1124 fold_range (r, s, q: get_global_range_query ());
1125 else
1126 gimple_range_global (v&: r, name);
1127 }
1128}
1129
1130// Get the range of NAME as it occurs on entry to block BB. Use MODE for
1131// lookups.
1132
1133void
1134ranger_cache::entry_range (vrange &r, tree name, basic_block bb,
1135 enum rfd_mode mode)
1136{
1137 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1138 {
1139 gimple_range_global (v&: r, name);
1140 return;
1141 }
1142
1143 // Look for the on-entry value of name in BB from the cache.
1144 // Otherwise pick up the best available global value.
1145 if (!m_on_entry.get_bb_range (r, name, bb))
1146 if (!range_from_dom (r, name, bb, mode))
1147 range_of_def (r, name);
1148}
1149
1150// Get the range of NAME as it occurs on exit from block BB. Use MODE for
1151// lookups.
1152
1153void
1154ranger_cache::exit_range (vrange &r, tree name, basic_block bb,
1155 enum rfd_mode mode)
1156{
1157 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1158 {
1159 gimple_range_global (v&: r, name);
1160 return;
1161 }
1162
1163 gimple *s = SSA_NAME_DEF_STMT (name);
1164 basic_block def_bb = gimple_bb (g: s);
1165 if (def_bb == bb)
1166 range_of_def (r, name, bb);
1167 else
1168 entry_range (r, name, bb, mode);
1169}
1170
1171// Get the range of NAME on edge E using MODE, return the result in R.
1172// Always returns a range and true.
1173
1174bool
1175ranger_cache::edge_range (vrange &r, edge e, tree name, enum rfd_mode mode)
1176{
1177 exit_range (r, name, bb: e->src, mode);
1178 // If this is not an abnormal edge, check for inferred ranges on exit.
1179 if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
1180 m_exit.maybe_adjust_range (r, name, bb: e->src);
1181 Value_Range er (TREE_TYPE (name));
1182 if (m_gori.outgoing_edge_range_p (r&: er, e, name, q&: *this))
1183 r.intersect (er);
1184 return true;
1185}
1186
1187
1188
1189// Implement range_of_expr.
1190
1191bool
1192ranger_cache::range_of_expr (vrange &r, tree name, gimple *stmt)
1193{
1194 if (!gimple_range_ssa_p (exp: name))
1195 {
1196 get_tree_range (v&: r, expr: name, stmt);
1197 return true;
1198 }
1199
1200 basic_block bb = gimple_bb (g: stmt);
1201 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1202 basic_block def_bb = gimple_bb (g: def_stmt);
1203
1204 if (bb == def_bb)
1205 range_of_def (r, name, bb);
1206 else
1207 entry_range (r, name, bb, mode: RFD_NONE);
1208 return true;
1209}
1210
1211
1212// Implement range_on_edge. Always return the best available range using
1213// the current cache values.
1214
1215bool
1216ranger_cache::range_on_edge (vrange &r, edge e, tree expr)
1217{
1218 if (gimple_range_ssa_p (exp: expr))
1219 return edge_range (r, e, name: expr, mode: RFD_NONE);
1220 return get_tree_range (v&: r, expr, NULL);
1221}
1222
1223// Return a static range for NAME on entry to basic block BB in R. If
1224// calc is true, fill any cache entries required between BB and the
1225// def block for NAME. Otherwise, return false if the cache is empty.
1226
1227bool
1228ranger_cache::block_range (vrange &r, basic_block bb, tree name, bool calc)
1229{
1230 gcc_checking_assert (gimple_range_ssa_p (name));
1231
1232 // If there are no range calculations anywhere in the IL, global range
1233 // applies everywhere, so don't bother caching it.
1234 if (!m_gori.has_edge_range_p (name))
1235 return false;
1236
1237 if (calc)
1238 {
1239 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1240 basic_block def_bb = NULL;
1241 if (def_stmt)
1242 def_bb = gimple_bb (g: def_stmt);;
1243 if (!def_bb)
1244 {
1245 // If we get to the entry block, this better be a default def
1246 // or range_on_entry was called for a block not dominated by
1247 // the def.
1248 gcc_checking_assert (SSA_NAME_IS_DEFAULT_DEF (name));
1249 def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1250 }
1251
1252 // There is no range on entry for the definition block.
1253 if (def_bb == bb)
1254 return false;
1255
1256 // Otherwise, go figure out what is known in predecessor blocks.
1257 fill_block_cache (name, bb, def_bb);
1258 gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
1259 }
1260 return m_on_entry.get_bb_range (r, name, bb);
1261}
1262
1263// If there is anything in the propagation update_list, continue
1264// processing NAME until the list of blocks is empty.
1265
1266void
1267ranger_cache::propagate_cache (tree name)
1268{
1269 basic_block bb;
1270 edge_iterator ei;
1271 edge e;
1272 tree type = TREE_TYPE (name);
1273 Value_Range new_range (type);
1274 Value_Range current_range (type);
1275 Value_Range e_range (type);
1276
1277 // Process each block by seeing if its calculated range on entry is
1278 // the same as its cached value. If there is a difference, update
1279 // the cache to reflect the new value, and check to see if any
1280 // successors have cache entries which may need to be checked for
1281 // updates.
1282
1283 while (!m_update->empty_p ())
1284 {
1285 bb = m_update->pop ();
1286 gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
1287 m_on_entry.get_bb_range (r&: current_range, name, bb);
1288
1289 if (DEBUG_RANGE_CACHE)
1290 {
1291 fprintf (stream: dump_file, format: "FWD visiting block %d for ", bb->index);
1292 print_generic_expr (dump_file, name, TDF_SLIM);
1293 fprintf (stream: dump_file, format: " starting range : ");
1294 current_range.dump (dump_file);
1295 fprintf (stream: dump_file, format: "\n");
1296 }
1297
1298 // Calculate the "new" range on entry by unioning the pred edges.
1299 new_range.set_undefined ();
1300 FOR_EACH_EDGE (e, ei, bb->preds)
1301 {
1302 edge_range (r&: e_range, e, name, mode: RFD_READ_ONLY);
1303 if (DEBUG_RANGE_CACHE)
1304 {
1305 fprintf (stream: dump_file, format: " edge %d->%d :", e->src->index, bb->index);
1306 e_range.dump (dump_file);
1307 fprintf (stream: dump_file, format: "\n");
1308 }
1309 new_range.union_ (r: e_range);
1310 if (new_range.varying_p ())
1311 break;
1312 }
1313
1314 // If the range on entry has changed, update it.
1315 if (new_range != current_range)
1316 {
1317 bool ok_p = m_on_entry.set_bb_range (name, bb, r: new_range);
1318 // If the cache couldn't set the value, mark it as failed.
1319 if (!ok_p)
1320 m_update->propagation_failed (bb);
1321 if (DEBUG_RANGE_CACHE)
1322 {
1323 if (!ok_p)
1324 {
1325 fprintf (stream: dump_file, format: " Cache failure to store value:");
1326 print_generic_expr (dump_file, name, TDF_SLIM);
1327 fprintf (stream: dump_file, format: " ");
1328 }
1329 else
1330 {
1331 fprintf (stream: dump_file, format: " Updating range to ");
1332 new_range.dump (dump_file);
1333 }
1334 fprintf (stream: dump_file, format: "\n Updating blocks :");
1335 }
1336 // Mark each successor that has a range to re-check its range
1337 FOR_EACH_EDGE (e, ei, bb->succs)
1338 if (m_on_entry.bb_range_p (name, bb: e->dest))
1339 {
1340 if (DEBUG_RANGE_CACHE)
1341 fprintf (stream: dump_file, format: " bb%d",e->dest->index);
1342 m_update->add (bb: e->dest);
1343 }
1344 if (DEBUG_RANGE_CACHE)
1345 fprintf (stream: dump_file, format: "\n");
1346 }
1347 }
1348 if (DEBUG_RANGE_CACHE)
1349 {
1350 fprintf (stream: dump_file, format: "DONE visiting blocks for ");
1351 print_generic_expr (dump_file, name, TDF_SLIM);
1352 fprintf (stream: dump_file, format: "\n");
1353 }
1354 m_update->clear_failures ();
1355}
1356
1357// Check to see if an update to the value for NAME in BB has any effect
1358// on values already in the on-entry cache for successor blocks.
1359// If it does, update them. Don't visit any blocks which don't have a cache
1360// entry.
1361
1362void
1363ranger_cache::propagate_updated_value (tree name, basic_block bb)
1364{
1365 edge e;
1366 edge_iterator ei;
1367
1368 // The update work list should be empty at this point.
1369 gcc_checking_assert (m_update->empty_p ());
1370 gcc_checking_assert (bb);
1371
1372 if (DEBUG_RANGE_CACHE)
1373 {
1374 fprintf (stream: dump_file, format: " UPDATE cache for ");
1375 print_generic_expr (dump_file, name, TDF_SLIM);
1376 fprintf (stream: dump_file, format: " in BB %d : successors : ", bb->index);
1377 }
1378 FOR_EACH_EDGE (e, ei, bb->succs)
1379 {
1380 // Only update active cache entries.
1381 if (m_on_entry.bb_range_p (name, bb: e->dest))
1382 {
1383 m_update->add (bb: e->dest);
1384 if (DEBUG_RANGE_CACHE)
1385 fprintf (stream: dump_file, format: " UPDATE: bb%d", e->dest->index);
1386 }
1387 }
1388 if (!m_update->empty_p ())
1389 {
1390 if (DEBUG_RANGE_CACHE)
1391 fprintf (stream: dump_file, format: "\n");
1392 propagate_cache (name);
1393 }
1394 else
1395 {
1396 if (DEBUG_RANGE_CACHE)
1397 fprintf (stream: dump_file, format: " : No updates!\n");
1398 }
1399}
1400
1401// Make sure that the range-on-entry cache for NAME is set for block BB.
1402// Work back through the CFG to DEF_BB ensuring the range is calculated
1403// on the block/edges leading back to that point.
1404
1405void
1406ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
1407{
1408 edge_iterator ei;
1409 edge e;
1410 tree type = TREE_TYPE (name);
1411 Value_Range block_result (type);
1412 Value_Range undefined (type);
1413
1414 // At this point we shouldn't be looking at the def, entry block.
1415 gcc_checking_assert (bb != def_bb && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
1416 gcc_checking_assert (m_workback.length () == 0);
1417
1418 // If the block cache is set, then we've already visited this block.
1419 if (m_on_entry.bb_range_p (name, bb))
1420 return;
1421
1422 if (DEBUG_RANGE_CACHE)
1423 {
1424 fprintf (stream: dump_file, format: "\n");
1425 print_generic_expr (dump_file, name, TDF_SLIM);
1426 fprintf (stream: dump_file, format: " : ");
1427 }
1428
1429 // Check if a dominators can supply the range.
1430 if (range_from_dom (r&: block_result, name, bb, RFD_FILL))
1431 {
1432 if (DEBUG_RANGE_CACHE)
1433 {
1434 fprintf (stream: dump_file, format: "Filled from dominator! : ");
1435 block_result.dump (dump_file);
1436 fprintf (stream: dump_file, format: "\n");
1437 }
1438 // See if any equivalences can refine it.
1439 // PR 109462, like 108139 below, a one way equivalence introduced
1440 // by a PHI node can also be through the definition side. Disallow it.
1441 if (m_oracle)
1442 {
1443 tree equiv_name;
1444 relation_kind rel;
1445 int prec = TYPE_PRECISION (type);
1446 FOR_EACH_PARTIAL_AND_FULL_EQUIV (m_oracle, bb, name, equiv_name, rel)
1447 {
1448 basic_block equiv_bb = gimple_bb (SSA_NAME_DEF_STMT (equiv_name));
1449
1450 // Ignore partial equivs that are smaller than this object.
1451 if (rel != VREL_EQ && prec > pe_to_bits (t: rel))
1452 continue;
1453
1454 // Check if the equiv has any ranges calculated.
1455 if (!m_gori.has_edge_range_p (name: equiv_name))
1456 continue;
1457
1458 // Check if the equiv definition dominates this block
1459 if (equiv_bb == bb ||
1460 (equiv_bb && !dominated_by_p (CDI_DOMINATORS, bb, equiv_bb)))
1461 continue;
1462
1463 if (DEBUG_RANGE_CACHE)
1464 {
1465 if (rel == VREL_EQ)
1466 fprintf (stream: dump_file, format: "Checking Equivalence (");
1467 else
1468 fprintf (stream: dump_file, format: "Checking Partial equiv (");
1469 print_relation (f: dump_file, rel);
1470 fprintf (stream: dump_file, format: ") ");
1471 print_generic_expr (dump_file, equiv_name, TDF_SLIM);
1472 fprintf (stream: dump_file, format: "\n");
1473 }
1474 Value_Range equiv_range (TREE_TYPE (equiv_name));
1475 if (range_from_dom (r&: equiv_range, name: equiv_name, bb, RFD_READ_ONLY))
1476 {
1477 if (rel != VREL_EQ)
1478 range_cast (r&: equiv_range, type);
1479 else
1480 adjust_equivalence_range (range&: equiv_range);
1481
1482 if (block_result.intersect (r: equiv_range))
1483 {
1484 if (DEBUG_RANGE_CACHE)
1485 {
1486 if (rel == VREL_EQ)
1487 fprintf (stream: dump_file, format: "Equivalence update! : ");
1488 else
1489 fprintf (stream: dump_file, format: "Partial equiv update! : ");
1490 print_generic_expr (dump_file, equiv_name, TDF_SLIM);
1491 fprintf (stream: dump_file, format: " has range : ");
1492 equiv_range.dump (dump_file);
1493 fprintf (stream: dump_file, format: " refining range to :");
1494 block_result.dump (dump_file);
1495 fprintf (stream: dump_file, format: "\n");
1496 }
1497 }
1498 }
1499 }
1500 }
1501
1502 m_on_entry.set_bb_range (name, bb, r: block_result);
1503 gcc_checking_assert (m_workback.length () == 0);
1504 return;
1505 }
1506
1507 // Visit each block back to the DEF. Initialize each one to UNDEFINED.
1508 // m_visited at the end will contain all the blocks that we needed to set
1509 // the range_on_entry cache for.
1510 m_workback.quick_push (obj: bb);
1511 undefined.set_undefined ();
1512 m_on_entry.set_bb_range (name, bb, r: undefined);
1513 gcc_checking_assert (m_update->empty_p ());
1514
1515 while (m_workback.length () > 0)
1516 {
1517 basic_block node = m_workback.pop ();
1518 if (DEBUG_RANGE_CACHE)
1519 {
1520 fprintf (stream: dump_file, format: "BACK visiting block %d for ", node->index);
1521 print_generic_expr (dump_file, name, TDF_SLIM);
1522 fprintf (stream: dump_file, format: "\n");
1523 }
1524
1525 FOR_EACH_EDGE (e, ei, node->preds)
1526 {
1527 basic_block pred = e->src;
1528 Value_Range r (TREE_TYPE (name));
1529
1530 if (DEBUG_RANGE_CACHE)
1531 fprintf (stream: dump_file, format: " %d->%d ",e->src->index, e->dest->index);
1532
1533 // If the pred block is the def block add this BB to update list.
1534 if (pred == def_bb)
1535 {
1536 m_update->add (bb: node);
1537 continue;
1538 }
1539
1540 // If the pred is entry but NOT def, then it is used before
1541 // defined, it'll get set to [] and no need to update it.
1542 if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1543 {
1544 if (DEBUG_RANGE_CACHE)
1545 fprintf (stream: dump_file, format: "entry: bail.");
1546 continue;
1547 }
1548
1549 // Regardless of whether we have visited pred or not, if the
1550 // pred has inferred ranges, revisit this block.
1551 // Don't search the DOM tree.
1552 if (m_exit.has_range_p (name, bb: pred))
1553 {
1554 if (DEBUG_RANGE_CACHE)
1555 fprintf (stream: dump_file, format: "Inferred range: update ");
1556 m_update->add (bb: node);
1557 }
1558
1559 // If the pred block already has a range, or if it can contribute
1560 // something new. Ie, the edge generates a range of some sort.
1561 if (m_on_entry.get_bb_range (r, name, bb: pred))
1562 {
1563 if (DEBUG_RANGE_CACHE)
1564 {
1565 fprintf (stream: dump_file, format: "has cache, ");
1566 r.dump (dump_file);
1567 fprintf (stream: dump_file, format: ", ");
1568 }
1569 if (!r.undefined_p () || m_gori.has_edge_range_p (name, e))
1570 {
1571 m_update->add (bb: node);
1572 if (DEBUG_RANGE_CACHE)
1573 fprintf (stream: dump_file, format: "update. ");
1574 }
1575 continue;
1576 }
1577
1578 if (DEBUG_RANGE_CACHE)
1579 fprintf (stream: dump_file, format: "pushing undefined pred block.\n");
1580 // If the pred hasn't been visited (has no range), add it to
1581 // the list.
1582 gcc_checking_assert (!m_on_entry.bb_range_p (name, pred));
1583 m_on_entry.set_bb_range (name, bb: pred, r: undefined);
1584 m_workback.quick_push (obj: pred);
1585 }
1586 }
1587
1588 if (DEBUG_RANGE_CACHE)
1589 fprintf (stream: dump_file, format: "\n");
1590
1591 // Now fill in the marked blocks with values.
1592 propagate_cache (name);
1593 if (DEBUG_RANGE_CACHE)
1594 fprintf (stream: dump_file, format: " Propagation update done.\n");
1595}
1596
1597// Resolve the range of BB if the dominators range is R by calculating incoming
1598// edges to this block. All lead back to the dominator so should be cheap.
1599// The range for BB is set and returned in R.
1600
1601void
1602ranger_cache::resolve_dom (vrange &r, tree name, basic_block bb)
1603{
1604 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1605 basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1606
1607 // if it doesn't already have a value, store the incoming range.
1608 if (!m_on_entry.bb_range_p (name, bb: dom_bb) && def_bb != dom_bb)
1609 {
1610 // If the range can't be store, don't try to accumulate
1611 // the range in PREV_BB due to excessive recalculations.
1612 if (!m_on_entry.set_bb_range (name, bb: dom_bb, r))
1613 return;
1614 }
1615 // With the dominator set, we should be able to cheaply query
1616 // each incoming edge now and accumulate the results.
1617 r.set_undefined ();
1618 edge e;
1619 edge_iterator ei;
1620 Value_Range er (TREE_TYPE (name));
1621 FOR_EACH_EDGE (e, ei, bb->preds)
1622 {
1623 // If the predecessor is dominated by this block, then there is a back
1624 // edge, and won't provide anything useful. We'll actually end up with
1625 // VARYING as we will not resolve this node.
1626 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1627 continue;
1628 edge_range (r&: er, e, name, mode: RFD_READ_ONLY);
1629 r.union_ (er);
1630 }
1631 // Set the cache in PREV_BB so it is not calculated again.
1632 m_on_entry.set_bb_range (name, bb, r);
1633}
1634
1635// Get the range of NAME from dominators of BB and return it in R. Search the
1636// dominator tree based on MODE.
1637
1638bool
1639ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
1640 enum rfd_mode mode)
1641{
1642 if (mode == RFD_NONE || !dom_info_available_p (CDI_DOMINATORS))
1643 return false;
1644
1645 // Search back to the definition block or entry block.
1646 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1647 if (def_bb == NULL)
1648 def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1649
1650 basic_block bb;
1651 basic_block prev_bb = start_bb;
1652
1653 // Track any inferred ranges seen.
1654 Value_Range infer (TREE_TYPE (name));
1655 infer.set_varying (TREE_TYPE (name));
1656
1657 // Range on entry to the DEF block should not be queried.
1658 gcc_checking_assert (start_bb != def_bb);
1659 unsigned start_limit = m_workback.length ();
1660
1661 // Default value is global range.
1662 get_global_range (r, name);
1663
1664 // The dominator of EXIT_BLOCK doesn't seem to be set, so at least handle
1665 // the common single exit cases.
1666 if (start_bb == EXIT_BLOCK_PTR_FOR_FN (cfun) && single_pred_p (bb: start_bb))
1667 bb = single_pred_edge (bb: start_bb)->src;
1668 else
1669 bb = get_immediate_dominator (CDI_DOMINATORS, start_bb);
1670
1671 // Search until a value is found, pushing blocks which may need calculating.
1672 for ( ; bb; prev_bb = bb, bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1673 {
1674 // Accumulate any block exit inferred ranges.
1675 m_exit.maybe_adjust_range (r&: infer, name, bb);
1676
1677 // This block has an outgoing range.
1678 if (m_gori.has_edge_range_p (name, bb))
1679 m_workback.quick_push (obj: prev_bb);
1680 else
1681 {
1682 // Normally join blocks don't carry any new range information on
1683 // incoming edges. If the first incoming edge to this block does
1684 // generate a range, calculate the ranges if all incoming edges
1685 // are also dominated by the dominator. (Avoids backedges which
1686 // will break the rule of moving only upward in the dominator tree).
1687 // If the first pred does not generate a range, then we will be
1688 // using the dominator range anyway, so that's all the check needed.
1689 if (EDGE_COUNT (prev_bb->preds) > 1
1690 && m_gori.has_edge_range_p (name, EDGE_PRED (prev_bb, 0)->src))
1691 {
1692 edge e;
1693 edge_iterator ei;
1694 bool all_dom = true;
1695 FOR_EACH_EDGE (e, ei, prev_bb->preds)
1696 if (e->src != bb
1697 && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
1698 {
1699 all_dom = false;
1700 break;
1701 }
1702 if (all_dom)
1703 m_workback.quick_push (obj: prev_bb);
1704 }
1705 }
1706
1707 if (def_bb == bb)
1708 break;
1709
1710 if (m_on_entry.get_bb_range (r, name, bb))
1711 break;
1712 }
1713
1714 if (DEBUG_RANGE_CACHE)
1715 {
1716 fprintf (stream: dump_file, format: "CACHE: BB %d DOM query for ", start_bb->index);
1717 print_generic_expr (dump_file, name, TDF_SLIM);
1718 fprintf (stream: dump_file, format: ", found ");
1719 r.dump (dump_file);
1720 if (bb)
1721 fprintf (stream: dump_file, format: " at BB%d\n", bb->index);
1722 else
1723 fprintf (stream: dump_file, format: " at function top\n");
1724 }
1725
1726 // Now process any blocks wit incoming edges that nay have adjustments.
1727 while (m_workback.length () > start_limit)
1728 {
1729 Value_Range er (TREE_TYPE (name));
1730 prev_bb = m_workback.pop ();
1731 if (!single_pred_p (bb: prev_bb))
1732 {
1733 // Non single pred means we need to cache a value in the dominator
1734 // so we can cheaply calculate incoming edges to this block, and
1735 // then store the resulting value. If processing mode is not
1736 // RFD_FILL, then the cache cant be stored to, so don't try.
1737 // Otherwise this becomes a quadratic timed calculation.
1738 if (mode == RFD_FILL)
1739 resolve_dom (r, name, bb: prev_bb);
1740 continue;
1741 }
1742
1743 edge e = single_pred_edge (bb: prev_bb);
1744 bb = e->src;
1745 if (m_gori.outgoing_edge_range_p (r&: er, e, name, q&: *this))
1746 {
1747 r.intersect (er);
1748 // If this is a normal edge, apply any inferred ranges.
1749 if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
1750 m_exit.maybe_adjust_range (r, name, bb);
1751
1752 if (DEBUG_RANGE_CACHE)
1753 {
1754 fprintf (stream: dump_file, format: "CACHE: Adjusted edge range for %d->%d : ",
1755 bb->index, prev_bb->index);
1756 r.dump (dump_file);
1757 fprintf (stream: dump_file, format: "\n");
1758 }
1759 }
1760 }
1761
1762 // Apply non-null if appropriate.
1763 if (!has_abnormal_call_or_eh_pred_edge_p (bb: start_bb))
1764 r.intersect (infer);
1765
1766 if (DEBUG_RANGE_CACHE)
1767 {
1768 fprintf (stream: dump_file, format: "CACHE: Range for DOM returns : ");
1769 r.dump (dump_file);
1770 fprintf (stream: dump_file, format: "\n");
1771 }
1772 return true;
1773}
1774
1775// This routine will register an inferred value in block BB, and possibly
1776// update the on-entry cache if appropriate.
1777
1778void
1779ranger_cache::register_inferred_value (const vrange &ir, tree name,
1780 basic_block bb)
1781{
1782 Value_Range r (TREE_TYPE (name));
1783 if (!m_on_entry.get_bb_range (r, name, bb))
1784 exit_range (r, name, bb, mode: RFD_READ_ONLY);
1785 if (r.intersect (r: ir))
1786 {
1787 m_on_entry.set_bb_range (name, bb, r);
1788 // If this range was invariant before, remove invariant.
1789 if (!m_gori.has_edge_range_p (name))
1790 m_gori.set_range_invariant (name, invariant: false);
1791 }
1792}
1793
1794// This routine is used during a block walk to adjust any inferred ranges
1795// of operands on stmt S.
1796
1797void
1798ranger_cache::apply_inferred_ranges (gimple *s)
1799{
1800 bool update = true;
1801
1802 basic_block bb = gimple_bb (g: s);
1803 gimple_infer_range infer(s);
1804 if (infer.num () == 0)
1805 return;
1806
1807 // Do not update the on-entry cache for block ending stmts.
1808 if (stmt_ends_bb_p (s))
1809 {
1810 edge_iterator ei;
1811 edge e;
1812 FOR_EACH_EDGE (e, ei, gimple_bb (s)->succs)
1813 if (!(e->flags & (EDGE_ABNORMAL|EDGE_EH)))
1814 break;
1815 if (e == NULL)
1816 update = false;
1817 }
1818
1819 for (unsigned x = 0; x < infer.num (); x++)
1820 {
1821 tree name = infer.name (index: x);
1822 m_exit.add_range (name, bb, r: infer.range (index: x));
1823 if (update)
1824 register_inferred_value (ir: infer.range (index: x), name, bb);
1825 }
1826}
1827

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