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

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