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