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