1 /* Gimple ranger SSA cache implementation.
2 Copyright (C) 2017-2022 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
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 "tree-cfg.h"
32 #include "target.h"
33 #include "attribs.h"
34 #include "gimple-iterator.h"
35 #include "gimple-walk.h"
36 #include "cfganal.h"
37
38 #define DEBUG_RANGE_CACHE (dump_file \
39 && (param_ranger_debug & RANGER_DEBUG_CACHE))
40
41 // During contructor, allocate the vector of ssa_names.
42
non_null_ref()43 non_null_ref::non_null_ref ()
44 {
45 m_nn.create (num_ssa_names);
46 m_nn.quick_grow_cleared (num_ssa_names);
47 bitmap_obstack_initialize (&m_bitmaps);
48 }
49
50 // Free any bitmaps which were allocated,a swell as the vector itself.
51
~non_null_ref()52 non_null_ref::~non_null_ref ()
53 {
54 bitmap_obstack_release (&m_bitmaps);
55 m_nn.release ();
56 }
57
58 // This routine will update NAME in BB to be nonnull if it is not already.
59 // return TRUE if the update happens.
60
61 bool
set_nonnull(basic_block bb,tree name)62 non_null_ref::set_nonnull (basic_block bb, tree name)
63 {
64 gcc_checking_assert (gimple_range_ssa_p (name)
65 && POINTER_TYPE_P (TREE_TYPE (name)));
66 // Only process when its not already set.
67 if (non_null_deref_p (name, bb, false))
68 return false;
69 bitmap_set_bit (m_nn[SSA_NAME_VERSION (name)], bb->index);
70 return true;
71 }
72
73 // Return true if NAME has a non-null dereference in block bb. If this is the
74 // first query for NAME, calculate the summary first.
75 // If SEARCH_DOM is true, the search the dominator tree as well.
76
77 bool
non_null_deref_p(tree name,basic_block bb,bool search_dom)78 non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom)
79 {
80 if (!POINTER_TYPE_P (TREE_TYPE (name)))
81 return false;
82
83 unsigned v = SSA_NAME_VERSION (name);
84 if (v >= m_nn.length ())
85 m_nn.safe_grow_cleared (num_ssa_names + 1);
86
87 if (!m_nn[v])
88 process_name (name);
89
90 if (bitmap_bit_p (m_nn[v], bb->index))
91 return true;
92
93 // See if any dominator has set non-zero.
94 if (search_dom && dom_info_available_p (CDI_DOMINATORS))
95 {
96 // Search back to the Def block, or the top, whichever is closer.
97 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
98 basic_block def_dom = def_bb
99 ? get_immediate_dominator (CDI_DOMINATORS, def_bb)
100 : NULL;
101 for ( ;
102 bb && bb != def_dom;
103 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
104 if (bitmap_bit_p (m_nn[v], bb->index))
105 return true;
106 }
107 return false;
108 }
109
110 // Allocate an populate the bitmap for NAME. An ON bit for a block
111 // index indicates there is a non-null reference in that block. In
112 // order to populate the bitmap, a quick run of all the immediate uses
113 // are made and the statement checked to see if a non-null dereference
114 // is made on that statement.
115
116 void
process_name(tree name)117 non_null_ref::process_name (tree name)
118 {
119 unsigned v = SSA_NAME_VERSION (name);
120 use_operand_p use_p;
121 imm_use_iterator iter;
122 bitmap b;
123
124 // Only tracked for pointers.
125 if (!POINTER_TYPE_P (TREE_TYPE (name)))
126 return;
127
128 // Already processed if a bitmap has been allocated.
129 if (m_nn[v])
130 return;
131
132 b = BITMAP_ALLOC (&m_bitmaps);
133
134 // Loop over each immediate use and see if it implies a non-null value.
135 FOR_EACH_IMM_USE_FAST (use_p, iter, name)
136 {
137 gimple *s = USE_STMT (use_p);
138 unsigned index = gimple_bb (s)->index;
139
140 // If bit is already set for this block, dont bother looking again.
141 if (bitmap_bit_p (b, index))
142 continue;
143
144 // If we can infer a nonnull range, then set the bit for this BB
145 if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)
146 && infer_nonnull_range (s, name))
147 bitmap_set_bit (b, index);
148 }
149
150 m_nn[v] = b;
151 }
152
153 // -------------------------------------------------------------------------
154
155 // This class represents the API into a cache of ranges for an SSA_NAME.
156 // Routines must be implemented to set, get, and query if a value is set.
157
158 class ssa_block_ranges
159 {
160 public:
161 virtual bool set_bb_range (const_basic_block bb, const irange &r) = 0;
162 virtual bool get_bb_range (irange &r, const_basic_block bb) = 0;
163 virtual bool bb_range_p (const_basic_block bb) = 0;
164
165 void dump(FILE *f);
166 };
167
168 // Print the list of known ranges for file F in a nice format.
169
170 void
dump(FILE * f)171 ssa_block_ranges::dump (FILE *f)
172 {
173 basic_block bb;
174 int_range_max r;
175
176 FOR_EACH_BB_FN (bb, cfun)
177 if (get_bb_range (r, bb))
178 {
179 fprintf (f, "BB%d -> ", bb->index);
180 r.dump (f);
181 fprintf (f, "\n");
182 }
183 }
184
185 // This class implements the range cache as a linear vector, indexed by BB.
186 // It caches a varying and undefined range which are used instead of
187 // allocating new ones each time.
188
189 class sbr_vector : public ssa_block_ranges
190 {
191 public:
192 sbr_vector (tree t, irange_allocator *allocator);
193
194 virtual bool set_bb_range (const_basic_block bb, const irange &r) OVERRIDE;
195 virtual bool get_bb_range (irange &r, const_basic_block bb) OVERRIDE;
196 virtual bool bb_range_p (const_basic_block bb) OVERRIDE;
197 protected:
198 irange **m_tab; // Non growing vector.
199 int m_tab_size;
200 int_range<2> m_varying;
201 int_range<2> m_undefined;
202 tree m_type;
203 irange_allocator *m_irange_allocator;
204 void grow ();
205 };
206
207
208 // Initialize a block cache for an ssa_name of type T.
209
sbr_vector(tree t,irange_allocator * allocator)210 sbr_vector::sbr_vector (tree t, irange_allocator *allocator)
211 {
212 gcc_checking_assert (TYPE_P (t));
213 m_type = t;
214 m_irange_allocator = allocator;
215 m_tab_size = last_basic_block_for_fn (cfun) + 1;
216 m_tab = (irange **)allocator->get_memory (m_tab_size * sizeof (irange *));
217 memset (m_tab, 0, m_tab_size * sizeof (irange *));
218
219 // Create the cached type range.
220 m_varying.set_varying (t);
221 m_undefined.set_undefined ();
222 }
223
224 // Grow the vector when the CFG has increased in size.
225
226 void
grow()227 sbr_vector::grow ()
228 {
229 int curr_bb_size = last_basic_block_for_fn (cfun);
230 gcc_checking_assert (curr_bb_size > m_tab_size);
231
232 // Increase the max of a)128, b)needed increase * 2, c)10% of current_size.
233 int inc = MAX ((curr_bb_size - m_tab_size) * 2, 128);
234 inc = MAX (inc, curr_bb_size / 10);
235 int new_size = inc + curr_bb_size;
236
237 // Allocate new memory, copy the old vector and clear the new space.
238 irange **t = (irange **)m_irange_allocator->get_memory (new_size
239 * sizeof (irange *));
240 memcpy (t, m_tab, m_tab_size * sizeof (irange *));
241 memset (t + m_tab_size, 0, (new_size - m_tab_size) * sizeof (irange *));
242
243 m_tab = t;
244 m_tab_size = new_size;
245 }
246
247 // Set the range for block BB to be R.
248
249 bool
set_bb_range(const_basic_block bb,const irange & r)250 sbr_vector::set_bb_range (const_basic_block bb, const irange &r)
251 {
252 irange *m;
253 if (bb->index >= m_tab_size)
254 grow ();
255 if (r.varying_p ())
256 m = &m_varying;
257 else if (r.undefined_p ())
258 m = &m_undefined;
259 else
260 m = m_irange_allocator->allocate (r);
261 m_tab[bb->index] = m;
262 return true;
263 }
264
265 // Return the range associated with block BB in R. Return false if
266 // there is no range.
267
268 bool
get_bb_range(irange & r,const_basic_block bb)269 sbr_vector::get_bb_range (irange &r, const_basic_block bb)
270 {
271 if (bb->index >= m_tab_size)
272 return false;
273 irange *m = m_tab[bb->index];
274 if (m)
275 {
276 r = *m;
277 return true;
278 }
279 return false;
280 }
281
282 // Return true if a range is present.
283
284 bool
bb_range_p(const_basic_block bb)285 sbr_vector::bb_range_p (const_basic_block bb)
286 {
287 if (bb->index < m_tab_size)
288 return m_tab[bb->index] != NULL;
289 return false;
290 }
291
292 // This class implements the on entry cache via a sparse bitmap.
293 // It uses the quad bit routines to access 4 bits at a time.
294 // A value of 0 (the default) means there is no entry, and a value of
295 // 1 thru SBR_NUM represents an element in the m_range vector.
296 // Varying is given the first value (1) and pre-cached.
297 // SBR_NUM + 1 represents the value of UNDEFINED, and is never stored.
298 // SBR_NUM is the number of values that can be cached.
299 // Indexes are 1..SBR_NUM and are stored locally at m_range[0..SBR_NUM-1]
300
301 #define SBR_NUM 14
302 #define SBR_UNDEF SBR_NUM + 1
303 #define SBR_VARYING 1
304
305 class sbr_sparse_bitmap : public ssa_block_ranges
306 {
307 public:
308 sbr_sparse_bitmap (tree t, irange_allocator *allocator, bitmap_obstack *bm);
309 virtual bool set_bb_range (const_basic_block bb, const irange &r) OVERRIDE;
310 virtual bool get_bb_range (irange &r, const_basic_block bb) OVERRIDE;
311 virtual bool bb_range_p (const_basic_block bb) OVERRIDE;
312 private:
313 void bitmap_set_quad (bitmap head, int quad, int quad_value);
314 int bitmap_get_quad (const_bitmap head, int quad);
315 irange_allocator *m_irange_allocator;
316 irange *m_range[SBR_NUM];
317 bitmap_head bitvec;
318 tree m_type;
319 };
320
321 // Initialize a block cache for an ssa_name of type T.
322
sbr_sparse_bitmap(tree t,irange_allocator * allocator,bitmap_obstack * bm)323 sbr_sparse_bitmap::sbr_sparse_bitmap (tree t, irange_allocator *allocator,
324 bitmap_obstack *bm)
325 {
326 gcc_checking_assert (TYPE_P (t));
327 m_type = t;
328 bitmap_initialize (&bitvec, bm);
329 bitmap_tree_view (&bitvec);
330 m_irange_allocator = allocator;
331 // Pre-cache varying.
332 m_range[0] = m_irange_allocator->allocate (2);
333 m_range[0]->set_varying (t);
334 // Pre-cache zero and non-zero values for pointers.
335 if (POINTER_TYPE_P (t))
336 {
337 m_range[1] = m_irange_allocator->allocate (2);
338 m_range[1]->set_nonzero (t);
339 m_range[2] = m_irange_allocator->allocate (2);
340 m_range[2]->set_zero (t);
341 }
342 else
343 m_range[1] = m_range[2] = NULL;
344 // Clear SBR_NUM entries.
345 for (int x = 3; x < SBR_NUM; x++)
346 m_range[x] = 0;
347 }
348
349 // Set 4 bit values in a sparse bitmap. This allows a bitmap to
350 // function as a sparse array of 4 bit values.
351 // QUAD is the index, QUAD_VALUE is the 4 bit value to set.
352
353 inline void
bitmap_set_quad(bitmap head,int quad,int quad_value)354 sbr_sparse_bitmap::bitmap_set_quad (bitmap head, int quad, int quad_value)
355 {
356 bitmap_set_aligned_chunk (head, quad, 4, (BITMAP_WORD) quad_value);
357 }
358
359 // Get a 4 bit value from a sparse bitmap. This allows a bitmap to
360 // function as a sparse array of 4 bit values.
361 // QUAD is the index.
362 inline int
bitmap_get_quad(const_bitmap head,int quad)363 sbr_sparse_bitmap::bitmap_get_quad (const_bitmap head, int quad)
364 {
365 return (int) bitmap_get_aligned_chunk (head, quad, 4);
366 }
367
368 // Set the range on entry to basic block BB to R.
369
370 bool
set_bb_range(const_basic_block bb,const irange & r)371 sbr_sparse_bitmap::set_bb_range (const_basic_block bb, const irange &r)
372 {
373 if (r.undefined_p ())
374 {
375 bitmap_set_quad (&bitvec, bb->index, SBR_UNDEF);
376 return true;
377 }
378
379 // Loop thru the values to see if R is already present.
380 for (int x = 0; x < SBR_NUM; x++)
381 if (!m_range[x] || r == *(m_range[x]))
382 {
383 if (!m_range[x])
384 m_range[x] = m_irange_allocator->allocate (r);
385 bitmap_set_quad (&bitvec, bb->index, x + 1);
386 return true;
387 }
388 // All values are taken, default to VARYING.
389 bitmap_set_quad (&bitvec, bb->index, SBR_VARYING);
390 return false;
391 }
392
393 // Return the range associated with block BB in R. Return false if
394 // there is no range.
395
396 bool
get_bb_range(irange & r,const_basic_block bb)397 sbr_sparse_bitmap::get_bb_range (irange &r, const_basic_block bb)
398 {
399 int value = bitmap_get_quad (&bitvec, bb->index);
400
401 if (!value)
402 return false;
403
404 gcc_checking_assert (value <= SBR_UNDEF);
405 if (value == SBR_UNDEF)
406 r.set_undefined ();
407 else
408 r = *(m_range[value - 1]);
409 return true;
410 }
411
412 // Return true if a range is present.
413
414 bool
bb_range_p(const_basic_block bb)415 sbr_sparse_bitmap::bb_range_p (const_basic_block bb)
416 {
417 return (bitmap_get_quad (&bitvec, bb->index) != 0);
418 }
419
420 // -------------------------------------------------------------------------
421
422 // Initialize the block cache.
423
block_range_cache()424 block_range_cache::block_range_cache ()
425 {
426 bitmap_obstack_initialize (&m_bitmaps);
427 m_ssa_ranges.create (0);
428 m_ssa_ranges.safe_grow_cleared (num_ssa_names);
429 m_irange_allocator = new irange_allocator;
430 }
431
432 // Remove any m_block_caches which have been created.
433
~block_range_cache()434 block_range_cache::~block_range_cache ()
435 {
436 delete m_irange_allocator;
437 // Release the vector itself.
438 m_ssa_ranges.release ();
439 bitmap_obstack_release (&m_bitmaps);
440 }
441
442 // Set the range for NAME on entry to block BB to R.
443 // If it has not been accessed yet, allocate it first.
444
445 bool
set_bb_range(tree name,const_basic_block bb,const irange & r)446 block_range_cache::set_bb_range (tree name, const_basic_block bb,
447 const irange &r)
448 {
449 unsigned v = SSA_NAME_VERSION (name);
450 if (v >= m_ssa_ranges.length ())
451 m_ssa_ranges.safe_grow_cleared (num_ssa_names + 1);
452
453 if (!m_ssa_ranges[v])
454 {
455 // Use sparse representation if there are too many basic blocks.
456 if (last_basic_block_for_fn (cfun) > param_evrp_sparse_threshold)
457 {
458 void *r = m_irange_allocator->get_memory (sizeof (sbr_sparse_bitmap));
459 m_ssa_ranges[v] = new (r) sbr_sparse_bitmap (TREE_TYPE (name),
460 m_irange_allocator,
461 &m_bitmaps);
462 }
463 else
464 {
465 // Otherwise use the default vector implemntation.
466 void *r = m_irange_allocator->get_memory (sizeof (sbr_vector));
467 m_ssa_ranges[v] = new (r) sbr_vector (TREE_TYPE (name),
468 m_irange_allocator);
469 }
470 }
471 return m_ssa_ranges[v]->set_bb_range (bb, r);
472 }
473
474
475 // Return a pointer to the ssa_block_cache for NAME. If it has not been
476 // accessed yet, return NULL.
477
478 inline ssa_block_ranges *
query_block_ranges(tree name)479 block_range_cache::query_block_ranges (tree name)
480 {
481 unsigned v = SSA_NAME_VERSION (name);
482 if (v >= m_ssa_ranges.length () || !m_ssa_ranges[v])
483 return NULL;
484 return m_ssa_ranges[v];
485 }
486
487
488
489 // Return the range for NAME on entry to BB in R. Return true if there
490 // is one.
491
492 bool
get_bb_range(irange & r,tree name,const_basic_block bb)493 block_range_cache::get_bb_range (irange &r, tree name, const_basic_block bb)
494 {
495 ssa_block_ranges *ptr = query_block_ranges (name);
496 if (ptr)
497 return ptr->get_bb_range (r, bb);
498 return false;
499 }
500
501 // Return true if NAME has a range set in block BB.
502
503 bool
bb_range_p(tree name,const_basic_block bb)504 block_range_cache::bb_range_p (tree name, const_basic_block bb)
505 {
506 ssa_block_ranges *ptr = query_block_ranges (name);
507 if (ptr)
508 return ptr->bb_range_p (bb);
509 return false;
510 }
511
512 // Print all known block caches to file F.
513
514 void
dump(FILE * f)515 block_range_cache::dump (FILE *f)
516 {
517 unsigned x;
518 for (x = 0; x < m_ssa_ranges.length (); ++x)
519 {
520 if (m_ssa_ranges[x])
521 {
522 fprintf (f, " Ranges for ");
523 print_generic_expr (f, ssa_name (x), TDF_NONE);
524 fprintf (f, ":\n");
525 m_ssa_ranges[x]->dump (f);
526 fprintf (f, "\n");
527 }
528 }
529 }
530
531 // Print all known ranges on entry to blobk BB to file F.
532
533 void
dump(FILE * f,basic_block bb,bool print_varying)534 block_range_cache::dump (FILE *f, basic_block bb, bool print_varying)
535 {
536 unsigned x;
537 int_range_max r;
538 bool summarize_varying = false;
539 for (x = 1; x < m_ssa_ranges.length (); ++x)
540 {
541 if (!gimple_range_ssa_p (ssa_name (x)))
542 continue;
543 if (m_ssa_ranges[x] && m_ssa_ranges[x]->get_bb_range (r, bb))
544 {
545 if (!print_varying && r.varying_p ())
546 {
547 summarize_varying = true;
548 continue;
549 }
550 print_generic_expr (f, ssa_name (x), TDF_NONE);
551 fprintf (f, "\t");
552 r.dump(f);
553 fprintf (f, "\n");
554 }
555 }
556 // If there were any varying entries, lump them all together.
557 if (summarize_varying)
558 {
559 fprintf (f, "VARYING_P on entry : ");
560 for (x = 1; x < num_ssa_names; ++x)
561 {
562 if (!gimple_range_ssa_p (ssa_name (x)))
563 continue;
564 if (m_ssa_ranges[x] && m_ssa_ranges[x]->get_bb_range (r, bb))
565 {
566 if (r.varying_p ())
567 {
568 print_generic_expr (f, ssa_name (x), TDF_NONE);
569 fprintf (f, " ");
570 }
571 }
572 }
573 fprintf (f, "\n");
574 }
575 }
576
577 // -------------------------------------------------------------------------
578
579 // Initialize a global cache.
580
ssa_global_cache()581 ssa_global_cache::ssa_global_cache ()
582 {
583 m_tab.create (0);
584 m_irange_allocator = new irange_allocator;
585 }
586
587 // Deconstruct a global cache.
588
~ssa_global_cache()589 ssa_global_cache::~ssa_global_cache ()
590 {
591 m_tab.release ();
592 delete m_irange_allocator;
593 }
594
595 // Retrieve the global range of NAME from cache memory if it exists.
596 // Return the value in R.
597
598 bool
get_global_range(irange & r,tree name) const599 ssa_global_cache::get_global_range (irange &r, tree name) const
600 {
601 unsigned v = SSA_NAME_VERSION (name);
602 if (v >= m_tab.length ())
603 return false;
604
605 irange *stow = m_tab[v];
606 if (!stow)
607 return false;
608 r = *stow;
609 return true;
610 }
611
612 // Set the range for NAME to R in the global cache.
613 // Return TRUE if there was already a range set, otherwise false.
614
615 bool
set_global_range(tree name,const irange & r)616 ssa_global_cache::set_global_range (tree name, const irange &r)
617 {
618 unsigned v = SSA_NAME_VERSION (name);
619 if (v >= m_tab.length ())
620 m_tab.safe_grow_cleared (num_ssa_names + 1);
621
622 irange *m = m_tab[v];
623 if (m && m->fits_p (r))
624 *m = r;
625 else
626 m_tab[v] = m_irange_allocator->allocate (r);
627 return m != NULL;
628 }
629
630 // Set the range for NAME to R in the glonbal cache.
631
632 void
clear_global_range(tree name)633 ssa_global_cache::clear_global_range (tree name)
634 {
635 unsigned v = SSA_NAME_VERSION (name);
636 if (v >= m_tab.length ())
637 m_tab.safe_grow_cleared (num_ssa_names + 1);
638 m_tab[v] = NULL;
639 }
640
641 // Clear the global cache.
642
643 void
clear()644 ssa_global_cache::clear ()
645 {
646 if (m_tab.address ())
647 memset (m_tab.address(), 0, m_tab.length () * sizeof (irange *));
648 }
649
650 // Dump the contents of the global cache to F.
651
652 void
dump(FILE * f)653 ssa_global_cache::dump (FILE *f)
654 {
655 /* Cleared after the table header has been printed. */
656 bool print_header = true;
657 for (unsigned x = 1; x < num_ssa_names; x++)
658 {
659 int_range_max r;
660 if (gimple_range_ssa_p (ssa_name (x)) &&
661 get_global_range (r, ssa_name (x)) && !r.varying_p ())
662 {
663 if (print_header)
664 {
665 /* Print the header only when there's something else
666 to print below. */
667 fprintf (f, "Non-varying global ranges:\n");
668 fprintf (f, "=========================:\n");
669 print_header = false;
670 }
671
672 print_generic_expr (f, ssa_name (x), TDF_NONE);
673 fprintf (f, " : ");
674 r.dump (f);
675 fprintf (f, "\n");
676 }
677 }
678
679 if (!print_header)
680 fputc ('\n', f);
681 }
682
683 // --------------------------------------------------------------------------
684
685
686 // This class will manage the timestamps for each ssa_name.
687 // When a value is calculated, the timestamp is set to the current time.
688 // Current time is then incremented. Any dependencies will already have
689 // been calculated, and will thus have older timestamps.
690 // If one of those values is ever calculated again, it will get a newer
691 // timestamp, and the "current_p" check will fail.
692
693 class temporal_cache
694 {
695 public:
696 temporal_cache ();
697 ~temporal_cache ();
698 bool current_p (tree name, tree dep1, tree dep2) const;
699 void set_timestamp (tree name);
700 void set_always_current (tree name);
701 private:
702 unsigned temporal_value (unsigned ssa) const;
703
704 unsigned m_current_time;
705 vec <unsigned> m_timestamp;
706 };
707
708 inline
temporal_cache()709 temporal_cache::temporal_cache ()
710 {
711 m_current_time = 1;
712 m_timestamp.create (0);
713 m_timestamp.safe_grow_cleared (num_ssa_names);
714 }
715
716 inline
~temporal_cache()717 temporal_cache::~temporal_cache ()
718 {
719 m_timestamp.release ();
720 }
721
722 // Return the timestamp value for SSA, or 0 if there isnt one.
723
724 inline unsigned
temporal_value(unsigned ssa) const725 temporal_cache::temporal_value (unsigned ssa) const
726 {
727 if (ssa >= m_timestamp.length ())
728 return 0;
729 return m_timestamp[ssa];
730 }
731
732 // Return TRUE if the timestampe for NAME is newer than any of its dependents.
733 // Up to 2 dependencies can be checked.
734
735 bool
current_p(tree name,tree dep1,tree dep2) const736 temporal_cache::current_p (tree name, tree dep1, tree dep2) const
737 {
738 unsigned ts = temporal_value (SSA_NAME_VERSION (name));
739 if (ts == 0)
740 return true;
741
742 // Any non-registered dependencies will have a value of 0 and thus be older.
743 // Return true if time is newer than either dependent.
744
745 if (dep1 && ts < temporal_value (SSA_NAME_VERSION (dep1)))
746 return false;
747 if (dep2 && ts < temporal_value (SSA_NAME_VERSION (dep2)))
748 return false;
749
750 return true;
751 }
752
753 // This increments the global timer and sets the timestamp for NAME.
754
755 inline void
set_timestamp(tree name)756 temporal_cache::set_timestamp (tree name)
757 {
758 unsigned v = SSA_NAME_VERSION (name);
759 if (v >= m_timestamp.length ())
760 m_timestamp.safe_grow_cleared (num_ssa_names + 20);
761 m_timestamp[v] = ++m_current_time;
762 }
763
764 // Set the timestamp to 0, marking it as "always up to date".
765
766 inline void
set_always_current(tree name)767 temporal_cache::set_always_current (tree name)
768 {
769 unsigned v = SSA_NAME_VERSION (name);
770 if (v >= m_timestamp.length ())
771 m_timestamp.safe_grow_cleared (num_ssa_names + 20);
772 m_timestamp[v] = 0;
773 }
774
775 // --------------------------------------------------------------------------
776
777 // This class provides an abstraction of a list of blocks to be updated
778 // by the cache. It is currently a stack but could be changed. It also
779 // maintains a list of blocks which have failed propagation, and does not
780 // enter any of those blocks into the list.
781
782 // A vector over the BBs is maintained, and an entry of 0 means it is not in
783 // a list. Otherwise, the entry is the next block in the list. -1 terminates
784 // the list. m_head points to the top of the list, -1 if the list is empty.
785
786 class update_list
787 {
788 public:
789 update_list ();
790 ~update_list ();
791 void add (basic_block bb);
792 basic_block pop ();
empty_p()793 inline bool empty_p () { return m_update_head == -1; }
clear_failures()794 inline void clear_failures () { bitmap_clear (m_propfail); }
propagation_failed(basic_block bb)795 inline void propagation_failed (basic_block bb)
796 { bitmap_set_bit (m_propfail, bb->index); }
797 private:
798 vec<int> m_update_list;
799 int m_update_head;
800 bitmap m_propfail;
801 };
802
803 // Create an update list.
804
update_list()805 update_list::update_list ()
806 {
807 m_update_list.create (0);
808 m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun) + 64);
809 m_update_head = -1;
810 m_propfail = BITMAP_ALLOC (NULL);
811 }
812
813 // Destroy an update list.
814
~update_list()815 update_list::~update_list ()
816 {
817 m_update_list.release ();
818 BITMAP_FREE (m_propfail);
819 }
820
821 // Add BB to the list of blocks to update, unless it's already in the list.
822
823 void
add(basic_block bb)824 update_list::add (basic_block bb)
825 {
826 int i = bb->index;
827 // If propagation has failed for BB, or its already in the list, don't
828 // add it again.
829 if ((unsigned)i >= m_update_list.length ())
830 m_update_list.safe_grow_cleared (i + 64);
831 if (!m_update_list[i] && !bitmap_bit_p (m_propfail, i))
832 {
833 if (empty_p ())
834 {
835 m_update_head = i;
836 m_update_list[i] = -1;
837 }
838 else
839 {
840 gcc_checking_assert (m_update_head > 0);
841 m_update_list[i] = m_update_head;
842 m_update_head = i;
843 }
844 }
845 }
846
847 // Remove a block from the list.
848
849 basic_block
pop()850 update_list::pop ()
851 {
852 gcc_checking_assert (!empty_p ());
853 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, m_update_head);
854 int pop = m_update_head;
855 m_update_head = m_update_list[pop];
856 m_update_list[pop] = 0;
857 return bb;
858 }
859
860 // --------------------------------------------------------------------------
861
ranger_cache(int not_executable_flag)862 ranger_cache::ranger_cache (int not_executable_flag)
863 : m_gori (not_executable_flag)
864 {
865 m_workback.create (0);
866 m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun));
867 m_temporal = new temporal_cache;
868 // If DOM info is available, spawn an oracle as well.
869 if (dom_info_available_p (CDI_DOMINATORS))
870 m_oracle = new dom_oracle ();
871 else
872 m_oracle = NULL;
873
874 unsigned x, lim = last_basic_block_for_fn (cfun);
875 // Calculate outgoing range info upfront. This will fully populate the
876 // m_maybe_variant bitmap which will help eliminate processing of names
877 // which never have their ranges adjusted.
878 for (x = 0; x < lim ; x++)
879 {
880 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, x);
881 if (bb)
882 m_gori.exports (bb);
883 }
884 m_update = new update_list ();
885 }
886
~ranger_cache()887 ranger_cache::~ranger_cache ()
888 {
889 delete m_update;
890 if (m_oracle)
891 delete m_oracle;
892 delete m_temporal;
893 m_workback.release ();
894 }
895
896 // Dump the global caches to file F. if GORI_DUMP is true, dump the
897 // gori map as well.
898
899 void
dump(FILE * f)900 ranger_cache::dump (FILE *f)
901 {
902 m_globals.dump (f);
903 fprintf (f, "\n");
904 }
905
906 // Dump the caches for basic block BB to file F.
907
908 void
dump_bb(FILE * f,basic_block bb)909 ranger_cache::dump_bb (FILE *f, basic_block bb)
910 {
911 m_gori.gori_map::dump (f, bb, false);
912 m_on_entry.dump (f, bb);
913 if (m_oracle)
914 m_oracle->dump (f, bb);
915 }
916
917 // Get the global range for NAME, and return in R. Return false if the
918 // global range is not set, and return the legacy global value in R.
919
920 bool
get_global_range(irange & r,tree name) const921 ranger_cache::get_global_range (irange &r, tree name) const
922 {
923 if (m_globals.get_global_range (r, name))
924 return true;
925 r = gimple_range_global (name);
926 return false;
927 }
928
929 // Get the global range for NAME, and return in R. Return false if the
930 // global range is not set, and R will contain the legacy global value.
931 // CURRENT_P is set to true if the value was in cache and not stale.
932 // Otherwise, set CURRENT_P to false and mark as it always current.
933 // If the global cache did not have a value, initialize it as well.
934 // After this call, the global cache will have a value.
935
936 bool
get_global_range(irange & r,tree name,bool & current_p)937 ranger_cache::get_global_range (irange &r, tree name, bool ¤t_p)
938 {
939 bool had_global = get_global_range (r, name);
940
941 // If there was a global value, set current flag, otherwise set a value.
942 current_p = false;
943 if (had_global)
944 current_p = r.singleton_p ()
945 || m_temporal->current_p (name, m_gori.depend1 (name),
946 m_gori.depend2 (name));
947 else
948 m_globals.set_global_range (name, r);
949
950 // If the existing value was not current, mark it as always current.
951 if (!current_p)
952 m_temporal->set_always_current (name);
953 return current_p;
954 }
955
956 // Set the global range of NAME to R and give it a timestamp.
957
958 void
set_global_range(tree name,const irange & r)959 ranger_cache::set_global_range (tree name, const irange &r)
960 {
961 if (m_globals.set_global_range (name, r))
962 {
963 // If there was already a range set, propagate the new value.
964 basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (name));
965 if (!bb)
966 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
967
968 if (DEBUG_RANGE_CACHE)
969 fprintf (dump_file, " GLOBAL :");
970
971 propagate_updated_value (name, bb);
972 }
973 // Constants no longer need to tracked. Any further refinement has to be
974 // undefined. Propagation works better with constants. PR 100512.
975 // Pointers which resolve to non-zero also do not need
976 // tracking in the cache as they will never change. See PR 98866.
977 // Timestamp must always be updated, or dependent calculations may
978 // not include this latest value. PR 100774.
979
980 if (r.singleton_p ()
981 || (POINTER_TYPE_P (TREE_TYPE (name)) && r.nonzero_p ()))
982 m_gori.set_range_invariant (name);
983 m_temporal->set_timestamp (name);
984 }
985
986 // Provide lookup for the gori-computes class to access the best known range
987 // of an ssa_name in any given basic block. Note, this does no additonal
988 // lookups, just accesses the data that is already known.
989
990 // Get the range of NAME when the def occurs in block BB. If BB is NULL
991 // get the best global value available.
992
993 void
range_of_def(irange & r,tree name,basic_block bb)994 ranger_cache::range_of_def (irange &r, tree name, basic_block bb)
995 {
996 gcc_checking_assert (gimple_range_ssa_p (name));
997 gcc_checking_assert (!bb || bb == gimple_bb (SSA_NAME_DEF_STMT (name)));
998
999 // Pick up the best global range available.
1000 if (!m_globals.get_global_range (r, name))
1001 {
1002 // If that fails, try to calculate the range using just global values.
1003 gimple *s = SSA_NAME_DEF_STMT (name);
1004 if (gimple_get_lhs (s) == name)
1005 fold_range (r, s, get_global_range_query ());
1006 else
1007 r = gimple_range_global (name);
1008 }
1009 }
1010
1011 // Get the range of NAME as it occurs on entry to block BB.
1012
1013 void
entry_range(irange & r,tree name,basic_block bb)1014 ranger_cache::entry_range (irange &r, tree name, basic_block bb)
1015 {
1016 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1017 {
1018 r = gimple_range_global (name);
1019 return;
1020 }
1021
1022 // Look for the on-entry value of name in BB from the cache.
1023 // Otherwise pick up the best available global value.
1024 if (!m_on_entry.get_bb_range (r, name, bb))
1025 range_of_def (r, name);
1026 }
1027
1028 // Get the range of NAME as it occurs on exit from block BB.
1029
1030 void
exit_range(irange & r,tree name,basic_block bb)1031 ranger_cache::exit_range (irange &r, tree name, basic_block bb)
1032 {
1033 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1034 {
1035 r = gimple_range_global (name);
1036 return;
1037 }
1038
1039 gimple *s = SSA_NAME_DEF_STMT (name);
1040 basic_block def_bb = gimple_bb (s);
1041 if (def_bb == bb)
1042 range_of_def (r, name, bb);
1043 else
1044 entry_range (r, name, bb);
1045 }
1046
1047
1048 // Implement range_of_expr.
1049
1050 bool
range_of_expr(irange & r,tree name,gimple * stmt)1051 ranger_cache::range_of_expr (irange &r, tree name, gimple *stmt)
1052 {
1053 if (!gimple_range_ssa_p (name))
1054 {
1055 get_tree_range (r, name, stmt);
1056 return true;
1057 }
1058
1059 basic_block bb = gimple_bb (stmt);
1060 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1061 basic_block def_bb = gimple_bb (def_stmt);
1062
1063 if (bb == def_bb)
1064 range_of_def (r, name, bb);
1065 else
1066 entry_range (r, name, bb);
1067 return true;
1068 }
1069
1070
1071 // Implement range_on_edge. Always return the best available range.
1072
1073 bool
range_on_edge(irange & r,edge e,tree expr)1074 ranger_cache::range_on_edge (irange &r, edge e, tree expr)
1075 {
1076 if (gimple_range_ssa_p (expr))
1077 {
1078 exit_range (r, expr, e->src);
1079 // If this is not an abnormal edge, check for a non-null exit.
1080 if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
1081 m_non_null.adjust_range (r, expr, e->src, false);
1082 int_range_max edge_range;
1083 if (m_gori.outgoing_edge_range_p (edge_range, e, expr, *this))
1084 r.intersect (edge_range);
1085 return true;
1086 }
1087
1088 return get_tree_range (r, expr, NULL);
1089 }
1090
1091
1092 // Return a static range for NAME on entry to basic block BB in R. If
1093 // calc is true, fill any cache entries required between BB and the
1094 // def block for NAME. Otherwise, return false if the cache is empty.
1095
1096 bool
block_range(irange & r,basic_block bb,tree name,bool calc)1097 ranger_cache::block_range (irange &r, basic_block bb, tree name, bool calc)
1098 {
1099 gcc_checking_assert (gimple_range_ssa_p (name));
1100
1101 // If there are no range calculations anywhere in the IL, global range
1102 // applies everywhere, so don't bother caching it.
1103 if (!m_gori.has_edge_range_p (name))
1104 return false;
1105
1106 if (calc)
1107 {
1108 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1109 basic_block def_bb = NULL;
1110 if (def_stmt)
1111 def_bb = gimple_bb (def_stmt);;
1112 if (!def_bb)
1113 {
1114 // If we get to the entry block, this better be a default def
1115 // or range_on_entry was called for a block not dominated by
1116 // the def.
1117 gcc_checking_assert (SSA_NAME_IS_DEFAULT_DEF (name));
1118 def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1119 }
1120
1121 // There is no range on entry for the definition block.
1122 if (def_bb == bb)
1123 return false;
1124
1125 // Otherwise, go figure out what is known in predecessor blocks.
1126 fill_block_cache (name, bb, def_bb);
1127 gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
1128 }
1129 return m_on_entry.get_bb_range (r, name, bb);
1130 }
1131
1132 // If there is anything in the propagation update_list, continue
1133 // processing NAME until the list of blocks is empty.
1134
1135 void
propagate_cache(tree name)1136 ranger_cache::propagate_cache (tree name)
1137 {
1138 basic_block bb;
1139 edge_iterator ei;
1140 edge e;
1141 int_range_max new_range;
1142 int_range_max current_range;
1143 int_range_max e_range;
1144
1145 // Process each block by seeing if its calculated range on entry is
1146 // the same as its cached value. If there is a difference, update
1147 // the cache to reflect the new value, and check to see if any
1148 // successors have cache entries which may need to be checked for
1149 // updates.
1150
1151 while (!m_update->empty_p ())
1152 {
1153 bb = m_update->pop ();
1154 gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
1155 m_on_entry.get_bb_range (current_range, name, bb);
1156
1157 if (DEBUG_RANGE_CACHE)
1158 {
1159 fprintf (dump_file, "FWD visiting block %d for ", bb->index);
1160 print_generic_expr (dump_file, name, TDF_SLIM);
1161 fprintf (dump_file, " starting range : ");
1162 current_range.dump (dump_file);
1163 fprintf (dump_file, "\n");
1164 }
1165
1166 // Calculate the "new" range on entry by unioning the pred edges.
1167 new_range.set_undefined ();
1168 FOR_EACH_EDGE (e, ei, bb->preds)
1169 {
1170 range_on_edge (e_range, e, name);
1171 if (DEBUG_RANGE_CACHE)
1172 {
1173 fprintf (dump_file, " edge %d->%d :", e->src->index, bb->index);
1174 e_range.dump (dump_file);
1175 fprintf (dump_file, "\n");
1176 }
1177 new_range.union_ (e_range);
1178 if (new_range.varying_p ())
1179 break;
1180 }
1181
1182 // If the range on entry has changed, update it.
1183 if (new_range != current_range)
1184 {
1185 bool ok_p = m_on_entry.set_bb_range (name, bb, new_range);
1186 // If the cache couldn't set the value, mark it as failed.
1187 if (!ok_p)
1188 m_update->propagation_failed (bb);
1189 if (DEBUG_RANGE_CACHE)
1190 {
1191 if (!ok_p)
1192 {
1193 fprintf (dump_file, " Cache failure to store value:");
1194 print_generic_expr (dump_file, name, TDF_SLIM);
1195 fprintf (dump_file, " ");
1196 }
1197 else
1198 {
1199 fprintf (dump_file, " Updating range to ");
1200 new_range.dump (dump_file);
1201 }
1202 fprintf (dump_file, "\n Updating blocks :");
1203 }
1204 // Mark each successor that has a range to re-check its range
1205 FOR_EACH_EDGE (e, ei, bb->succs)
1206 if (m_on_entry.bb_range_p (name, e->dest))
1207 {
1208 if (DEBUG_RANGE_CACHE)
1209 fprintf (dump_file, " bb%d",e->dest->index);
1210 m_update->add (e->dest);
1211 }
1212 if (DEBUG_RANGE_CACHE)
1213 fprintf (dump_file, "\n");
1214 }
1215 }
1216 if (DEBUG_RANGE_CACHE)
1217 {
1218 fprintf (dump_file, "DONE visiting blocks for ");
1219 print_generic_expr (dump_file, name, TDF_SLIM);
1220 fprintf (dump_file, "\n");
1221 }
1222 m_update->clear_failures ();
1223 }
1224
1225 // Check to see if an update to the value for NAME in BB has any effect
1226 // on values already in the on-entry cache for successor blocks.
1227 // If it does, update them. Don't visit any blocks which dont have a cache
1228 // entry.
1229
1230 void
propagate_updated_value(tree name,basic_block bb)1231 ranger_cache::propagate_updated_value (tree name, basic_block bb)
1232 {
1233 edge e;
1234 edge_iterator ei;
1235
1236 // The update work list should be empty at this point.
1237 gcc_checking_assert (m_update->empty_p ());
1238 gcc_checking_assert (bb);
1239
1240 if (DEBUG_RANGE_CACHE)
1241 {
1242 fprintf (dump_file, " UPDATE cache for ");
1243 print_generic_expr (dump_file, name, TDF_SLIM);
1244 fprintf (dump_file, " in BB %d : successors : ", bb->index);
1245 }
1246 FOR_EACH_EDGE (e, ei, bb->succs)
1247 {
1248 // Only update active cache entries.
1249 if (m_on_entry.bb_range_p (name, e->dest))
1250 {
1251 m_update->add (e->dest);
1252 if (DEBUG_RANGE_CACHE)
1253 fprintf (dump_file, " UPDATE: bb%d", e->dest->index);
1254 }
1255 }
1256 if (!m_update->empty_p ())
1257 {
1258 if (DEBUG_RANGE_CACHE)
1259 fprintf (dump_file, "\n");
1260 propagate_cache (name);
1261 }
1262 else
1263 {
1264 if (DEBUG_RANGE_CACHE)
1265 fprintf (dump_file, " : No updates!\n");
1266 }
1267 }
1268
1269 // Make sure that the range-on-entry cache for NAME is set for block BB.
1270 // Work back through the CFG to DEF_BB ensuring the range is calculated
1271 // on the block/edges leading back to that point.
1272
1273 void
fill_block_cache(tree name,basic_block bb,basic_block def_bb)1274 ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
1275 {
1276 edge_iterator ei;
1277 edge e;
1278 int_range_max block_result;
1279 int_range_max undefined;
1280
1281 // At this point we shouldn't be looking at the def, entry or exit block.
1282 gcc_checking_assert (bb != def_bb && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
1283 bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
1284
1285 // If the block cache is set, then we've already visited this block.
1286 if (m_on_entry.bb_range_p (name, bb))
1287 return;
1288
1289 // Visit each block back to the DEF. Initialize each one to UNDEFINED.
1290 // m_visited at the end will contain all the blocks that we needed to set
1291 // the range_on_entry cache for.
1292 m_workback.truncate (0);
1293 m_workback.quick_push (bb);
1294 undefined.set_undefined ();
1295 m_on_entry.set_bb_range (name, bb, undefined);
1296 gcc_checking_assert (m_update->empty_p ());
1297
1298 if (DEBUG_RANGE_CACHE)
1299 {
1300 fprintf (dump_file, "\n");
1301 print_generic_expr (dump_file, name, TDF_SLIM);
1302 fprintf (dump_file, " : ");
1303 }
1304
1305 // If there are dominators, check if a dominators can supply the range.
1306 if (dom_info_available_p (CDI_DOMINATORS)
1307 && range_from_dom (block_result, name, bb))
1308 {
1309 m_on_entry.set_bb_range (name, bb, block_result);
1310 if (DEBUG_RANGE_CACHE)
1311 {
1312 fprintf (dump_file, "Filled from dominator! : ");
1313 block_result.dump (dump_file);
1314 fprintf (dump_file, "\n");
1315 }
1316 return;
1317 }
1318
1319 while (m_workback.length () > 0)
1320 {
1321 basic_block node = m_workback.pop ();
1322 if (DEBUG_RANGE_CACHE)
1323 {
1324 fprintf (dump_file, "BACK visiting block %d for ", node->index);
1325 print_generic_expr (dump_file, name, TDF_SLIM);
1326 fprintf (dump_file, "\n");
1327 }
1328
1329 FOR_EACH_EDGE (e, ei, node->preds)
1330 {
1331 basic_block pred = e->src;
1332 int_range_max r;
1333
1334 if (DEBUG_RANGE_CACHE)
1335 fprintf (dump_file, " %d->%d ",e->src->index, e->dest->index);
1336
1337 // If the pred block is the def block add this BB to update list.
1338 if (pred == def_bb)
1339 {
1340 m_update->add (node);
1341 continue;
1342 }
1343
1344 // If the pred is entry but NOT def, then it is used before
1345 // defined, it'll get set to [] and no need to update it.
1346 if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1347 {
1348 if (DEBUG_RANGE_CACHE)
1349 fprintf (dump_file, "entry: bail.");
1350 continue;
1351 }
1352
1353 // Regardless of whether we have visited pred or not, if the
1354 // pred has a non-null reference, revisit this block.
1355 // Don't search the DOM tree.
1356 if (m_non_null.non_null_deref_p (name, pred, false))
1357 {
1358 if (DEBUG_RANGE_CACHE)
1359 fprintf (dump_file, "nonnull: update ");
1360 m_update->add (node);
1361 }
1362
1363 // If the pred block already has a range, or if it can contribute
1364 // something new. Ie, the edge generates a range of some sort.
1365 if (m_on_entry.get_bb_range (r, name, pred))
1366 {
1367 if (DEBUG_RANGE_CACHE)
1368 {
1369 fprintf (dump_file, "has cache, ");
1370 r.dump (dump_file);
1371 fprintf (dump_file, ", ");
1372 }
1373 if (!r.undefined_p () || m_gori.has_edge_range_p (name, e))
1374 {
1375 m_update->add (node);
1376 if (DEBUG_RANGE_CACHE)
1377 fprintf (dump_file, "update. ");
1378 }
1379 continue;
1380 }
1381
1382 if (DEBUG_RANGE_CACHE)
1383 fprintf (dump_file, "pushing undefined pred block.\n");
1384 // If the pred hasn't been visited (has no range), add it to
1385 // the list.
1386 gcc_checking_assert (!m_on_entry.bb_range_p (name, pred));
1387 m_on_entry.set_bb_range (name, pred, undefined);
1388 m_workback.quick_push (pred);
1389 }
1390 }
1391
1392 if (DEBUG_RANGE_CACHE)
1393 fprintf (dump_file, "\n");
1394
1395 // Now fill in the marked blocks with values.
1396 propagate_cache (name);
1397 if (DEBUG_RANGE_CACHE)
1398 fprintf (dump_file, " Propagation update done.\n");
1399 }
1400
1401
1402 // Get the range of NAME from dominators of BB and return it in R.
1403
1404 bool
range_from_dom(irange & r,tree name,basic_block start_bb)1405 ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb)
1406 {
1407 if (!dom_info_available_p (CDI_DOMINATORS))
1408 return false;
1409
1410 // Search back to the definition block or entry block.
1411 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1412 if (def_bb == NULL)
1413 def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1414
1415 basic_block bb;
1416 basic_block prev_bb = start_bb;
1417 // Flag if we encounter a block with non-null set.
1418 bool non_null = false;
1419
1420 // Range on entry to the DEF block should not be queried.
1421 gcc_checking_assert (start_bb != def_bb);
1422 m_workback.truncate (0);
1423
1424 // Default value is global range.
1425 get_global_range (r, name);
1426
1427 // Search until a value is found, pushing outgoing edges encountered.
1428 for (bb = get_immediate_dominator (CDI_DOMINATORS, start_bb);
1429 bb;
1430 prev_bb = bb, bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1431 {
1432 if (!non_null)
1433 non_null |= m_non_null.non_null_deref_p (name, bb, false);
1434
1435 // This block has an outgoing range.
1436 if (m_gori.has_edge_range_p (name, bb))
1437 {
1438 // Only outgoing ranges to single_pred blocks are dominated by
1439 // outgoing edge ranges, so only those need to be considered.
1440 edge e = find_edge (bb, prev_bb);
1441 if (e && single_pred_p (prev_bb))
1442 m_workback.quick_push (prev_bb);
1443 }
1444
1445 if (def_bb == bb)
1446 break;
1447
1448 if (m_on_entry.get_bb_range (r, name, bb))
1449 break;
1450 }
1451
1452 if (DEBUG_RANGE_CACHE)
1453 {
1454 fprintf (dump_file, "CACHE: BB %d DOM query, found ", start_bb->index);
1455 r.dump (dump_file);
1456 if (bb)
1457 fprintf (dump_file, " at BB%d\n", bb->index);
1458 else
1459 fprintf (dump_file, " at function top\n");
1460 }
1461
1462 // Now process any outgoing edges that we seen along the way.
1463 while (m_workback.length () > 0)
1464 {
1465 int_range_max edge_range;
1466 prev_bb = m_workback.pop ();
1467 edge e = single_pred_edge (prev_bb);
1468 bb = e->src;
1469
1470 if (m_gori.outgoing_edge_range_p (edge_range, e, name, *this))
1471 {
1472 r.intersect (edge_range);
1473 if (r.varying_p () && ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0))
1474 {
1475 if (m_non_null.non_null_deref_p (name, bb, false))
1476 {
1477 gcc_checking_assert (POINTER_TYPE_P (TREE_TYPE (name)));
1478 r.set_nonzero (TREE_TYPE (name));
1479 }
1480 }
1481 if (DEBUG_RANGE_CACHE)
1482 {
1483 fprintf (dump_file, "CACHE: Adjusted edge range for %d->%d : ",
1484 bb->index, prev_bb->index);
1485 r.dump (dump_file);
1486 fprintf (dump_file, "\n");
1487 }
1488 }
1489 }
1490
1491 // Apply non-null if appropriate.
1492 if (non_null && r.varying_p ()
1493 && !has_abnormal_call_or_eh_pred_edge_p (start_bb))
1494 {
1495 gcc_checking_assert (POINTER_TYPE_P (TREE_TYPE (name)));
1496 r.set_nonzero (TREE_TYPE (name));
1497 }
1498 if (DEBUG_RANGE_CACHE)
1499 {
1500 fprintf (dump_file, "CACHE: Range for DOM returns : ");
1501 r.dump (dump_file);
1502 fprintf (dump_file, "\n");
1503 }
1504 return true;
1505 }
1506
1507 // This routine will update NAME in block BB to the nonnull state.
1508 // It will then update the on-entry cache for this block to be non-null
1509 // if it isn't already.
1510
1511 void
update_to_nonnull(basic_block bb,tree name)1512 ranger_cache::update_to_nonnull (basic_block bb, tree name)
1513 {
1514 tree type = TREE_TYPE (name);
1515 if (gimple_range_ssa_p (name) && POINTER_TYPE_P (type))
1516 {
1517 m_non_null.set_nonnull (bb, name);
1518 // Update the on-entry cache for BB to be non-zero. Note this can set
1519 // the on entry value in the DEF block, which can override the def.
1520 int_range_max r;
1521 exit_range (r, name, bb);
1522 if (r.varying_p ())
1523 {
1524 r.set_nonzero (type);
1525 m_on_entry.set_bb_range (name, bb, r);
1526 }
1527 }
1528 }
1529
1530 // Adapted from infer_nonnull_range_by_dereference and check_loadstore
1531 // to process nonnull ssa_name OP in S. DATA contains the ranger_cache.
1532
1533 static bool
non_null_loadstore(gimple * s,tree op,tree,void * data)1534 non_null_loadstore (gimple *s, tree op, tree, void *data)
1535 {
1536 if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF)
1537 {
1538 /* Some address spaces may legitimately dereference zero. */
1539 addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op));
1540 if (!targetm.addr_space.zero_address_valid (as))
1541 {
1542 tree ssa = TREE_OPERAND (op, 0);
1543 basic_block bb = gimple_bb (s);
1544 ((ranger_cache *)data)->update_to_nonnull (bb, ssa);
1545 }
1546 }
1547 return false;
1548 }
1549
1550 // This routine is used during a block walk to move the state of non-null for
1551 // any operands on stmt S to nonnull.
1552
1553 void
block_apply_nonnull(gimple * s)1554 ranger_cache::block_apply_nonnull (gimple *s)
1555 {
1556 if (!flag_delete_null_pointer_checks)
1557 return;
1558 if (is_a<gphi *> (s))
1559 return;
1560 if (gimple_code (s) == GIMPLE_ASM || gimple_clobber_p (s))
1561 return;
1562 if (is_a<gcall *> (s))
1563 {
1564 tree fntype = gimple_call_fntype (s);
1565 bitmap nonnullargs = get_nonnull_args (fntype);
1566 // Process any non-null arguments
1567 if (nonnullargs)
1568 {
1569 basic_block bb = gimple_bb (s);
1570 for (unsigned i = 0; i < gimple_call_num_args (s); i++)
1571 {
1572 if (bitmap_empty_p (nonnullargs) || bitmap_bit_p (nonnullargs, i))
1573 {
1574 tree op = gimple_call_arg (s, i);
1575 update_to_nonnull (bb, op);
1576 }
1577 }
1578 BITMAP_FREE (nonnullargs);
1579 }
1580 // Fallthru and walk load/store ops now.
1581 }
1582 walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore,
1583 non_null_loadstore);
1584 }
1585