Branch data Line data Source code
1 : : /* Gimple ranger SSA cache implementation.
2 : : Copyright (C) 2017-2024 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 : 24060934 : 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 : 24049654 : sbr_vector::sbr_vector (tree t, vrange_allocator *allocator, bool zero_p)
102 : 24049654 : : ssa_block_ranges (t)
103 : : {
104 : 24049654 : gcc_checking_assert (TYPE_P (t));
105 : 24049654 : m_type = t;
106 : 24049654 : m_zero_p = zero_p;
107 : 24049654 : m_range_allocator = allocator;
108 : 24049654 : m_tab_size = last_basic_block_for_fn (cfun) + 1;
109 : 48099308 : m_tab = static_cast <vrange_storage **>
110 : 24049654 : (allocator->alloc (m_tab_size * sizeof (vrange_storage *)));
111 : 24049654 : if (zero_p)
112 : 21203712 : memset (m_tab, 0, m_tab_size * sizeof (vrange *));
113 : :
114 : : // Create the cached type range.
115 : 24049654 : m_varying = m_range_allocator->clone_varying (t);
116 : 24049654 : m_undefined = m_range_allocator->clone_undefined (t);
117 : 24049654 : }
118 : :
119 : : // Grow the vector when the CFG has increased in size.
120 : :
121 : : void
122 : 0 : sbr_vector::grow ()
123 : : {
124 : 0 : int curr_bb_size = last_basic_block_for_fn (cfun);
125 : 0 : 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 : 0 : int inc = MAX ((curr_bb_size - m_tab_size) * 2, 128);
129 : 0 : inc = MAX (inc, curr_bb_size / 10);
130 : 0 : int new_size = inc + curr_bb_size;
131 : :
132 : : // Allocate new memory, copy the old vector and clear the new space.
133 : 0 : vrange_storage **t = static_cast <vrange_storage **>
134 : 0 : (m_range_allocator->alloc (new_size * sizeof (vrange_storage *)));
135 : 0 : memcpy (t, m_tab, m_tab_size * sizeof (vrange_storage *));
136 : 0 : if (m_zero_p)
137 : 0 : memset (t + m_tab_size, 0, (new_size - m_tab_size) * sizeof (vrange_storage *));
138 : :
139 : 0 : m_tab = t;
140 : 0 : m_tab_size = new_size;
141 : 0 : }
142 : :
143 : : // Set the range for block BB to be R.
144 : :
145 : : bool
146 : 53918660 : sbr_vector::set_bb_range (const_basic_block bb, const vrange &r)
147 : : {
148 : 53918660 : vrange_storage *m;
149 : 53918660 : if (bb->index >= m_tab_size)
150 : 0 : grow ();
151 : 53918660 : if (r.varying_p ())
152 : 18307542 : m = m_varying;
153 : 35611118 : else if (r.undefined_p ())
154 : 258525 : m = m_undefined;
155 : : else
156 : 35352593 : m = m_range_allocator->clone (r);
157 : 53918660 : m_tab[bb->index] = m;
158 : 53918660 : 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 : 240485077 : sbr_vector::get_bb_range (vrange &r, const_basic_block bb)
166 : : {
167 : 240485077 : if (bb->index >= m_tab_size)
168 : : return false;
169 : 240485075 : vrange_storage *m = m_tab[bb->index];
170 : 240485075 : if (m)
171 : : {
172 : 180532874 : m->get_vrange (r, m_type);
173 : 180532874 : return true;
174 : : }
175 : : return false;
176 : : }
177 : :
178 : : // Return true if a range is present.
179 : :
180 : : bool
181 : 185858714 : sbr_vector::bb_range_p (const_basic_block bb)
182 : : {
183 : 185858714 : if (bb->index < m_tab_size)
184 : 185858714 : return m_tab[bb->index] != NULL;
185 : : return false;
186 : : }
187 : :
188 : : // Like an sbr_vector, except it uses a bitmap to manage whetehr vale is set
189 : : // or not rather than cleared memory.
190 : :
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 : 2845942 : sbr_lazy_vector::sbr_lazy_vector (tree t, vrange_allocator *allocator,
204 : 2845942 : bitmap_obstack *bm)
205 : 2845942 : : sbr_vector (t, allocator, false)
206 : : {
207 : 2845942 : m_has_value = BITMAP_ALLOC (bm);
208 : 2845942 : }
209 : :
210 : : bool
211 : 7185650 : sbr_lazy_vector::set_bb_range (const_basic_block bb, const vrange &r)
212 : : {
213 : 7185650 : sbr_vector::set_bb_range (bb, r);
214 : 7185650 : bitmap_set_bit (m_has_value, bb->index);
215 : 7185650 : return true;
216 : : }
217 : :
218 : : bool
219 : 220035041 : sbr_lazy_vector::get_bb_range (vrange &r, const_basic_block bb)
220 : : {
221 : 220035041 : if (bitmap_bit_p (m_has_value, bb->index))
222 : 25967346 : return sbr_vector::get_bb_range (r, bb);
223 : : return false;
224 : : }
225 : :
226 : : bool
227 : 30186833 : sbr_lazy_vector::bb_range_p (const_basic_block bb)
228 : : {
229 : 30186833 : 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 : 11280 : sbr_sparse_bitmap::sbr_sparse_bitmap (tree t, vrange_allocator *allocator,
264 : 11280 : bitmap_obstack *bm)
265 : 11280 : : ssa_block_ranges (t)
266 : : {
267 : 11280 : gcc_checking_assert (TYPE_P (t));
268 : 11280 : m_type = t;
269 : 11280 : bitmap_initialize (&bitvec, bm);
270 : 11280 : bitmap_tree_view (&bitvec);
271 : 11280 : m_range_allocator = allocator;
272 : : // Pre-cache varying.
273 : 11280 : m_range[0] = m_range_allocator->clone_varying (t);
274 : : // Pre-cache zero and non-zero values for pointers.
275 : 11280 : if (POINTER_TYPE_P (t))
276 : : {
277 : 253 : prange nonzero;
278 : 253 : nonzero.set_nonzero (t);
279 : 253 : m_range[1] = m_range_allocator->clone (nonzero);
280 : 253 : prange zero;
281 : 253 : zero.set_zero (t);
282 : 253 : m_range[2] = m_range_allocator->clone (zero);
283 : 253 : }
284 : : else
285 : 11027 : m_range[1] = m_range[2] = NULL;
286 : : // Clear SBR_NUM entries.
287 : 135360 : for (int x = 3; x < SBR_NUM; x++)
288 : 124080 : m_range[x] = 0;
289 : 11280 : }
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 : 291882 : sbr_sparse_bitmap::bitmap_set_quad (bitmap head, int quad, int quad_value)
297 : : {
298 : 291882 : 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 : 13047616 : sbr_sparse_bitmap::bitmap_get_quad (const_bitmap head, int quad)
306 : : {
307 : 26095232 : 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 : 291882 : sbr_sparse_bitmap::set_bb_range (const_basic_block bb, const vrange &r)
314 : : {
315 : 291882 : if (r.undefined_p ())
316 : : {
317 : 0 : bitmap_set_quad (&bitvec, bb->index, SBR_UNDEF);
318 : 0 : return true;
319 : : }
320 : :
321 : : // Loop thru the values to see if R is already present.
322 : 480198 : for (int x = 0; x < SBR_NUM; x++)
323 : 469177 : if (!m_range[x] || m_range[x]->equal_p (r))
324 : : {
325 : 280861 : if (!m_range[x])
326 : 8804 : m_range[x] = m_range_allocator->clone (r);
327 : 280861 : bitmap_set_quad (&bitvec, bb->index, x + 1);
328 : 280861 : return true;
329 : : }
330 : : // All values are taken, default to VARYING.
331 : 11021 : bitmap_set_quad (&bitvec, bb->index, SBR_VARYING);
332 : 11021 : 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 : 11251020 : sbr_sparse_bitmap::get_bb_range (vrange &r, const_basic_block bb)
340 : : {
341 : 11251020 : int value = bitmap_get_quad (&bitvec, bb->index);
342 : :
343 : 11251020 : if (!value)
344 : : return false;
345 : :
346 : 1427750 : gcc_checking_assert (value <= SBR_UNDEF);
347 : 1427750 : if (value == SBR_UNDEF)
348 : 0 : r.set_undefined ();
349 : : else
350 : 1427750 : 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 : 1796596 : sbr_sparse_bitmap::bb_range_p (const_basic_block bb)
358 : : {
359 : 1796596 : return (bitmap_get_quad (&bitvec, bb->index) != 0);
360 : : }
361 : :
362 : : // -------------------------------------------------------------------------
363 : :
364 : : // Initialize the block cache.
365 : :
366 : 24573651 : block_range_cache::block_range_cache ()
367 : : {
368 : 24573651 : bitmap_obstack_initialize (&m_bitmaps);
369 : 24573651 : m_ssa_ranges.create (0);
370 : 49147302 : m_ssa_ranges.safe_grow_cleared (num_ssa_names);
371 : 24573651 : m_range_allocator = new vrange_allocator;
372 : 24573651 : }
373 : :
374 : : // Remove any m_block_caches which have been created.
375 : :
376 : 24573651 : block_range_cache::~block_range_cache ()
377 : : {
378 : 24573651 : delete m_range_allocator;
379 : : // Release the vector itself.
380 : 24573651 : m_ssa_ranges.release ();
381 : 24573651 : bitmap_obstack_release (&m_bitmaps);
382 : 24573651 : }
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 : 54210542 : block_range_cache::set_bb_range (tree name, const_basic_block bb,
389 : : const vrange &r)
390 : : {
391 : 54210542 : unsigned v = SSA_NAME_VERSION (name);
392 : 54210542 : if (v >= m_ssa_ranges.length ())
393 : 2 : m_ssa_ranges.safe_grow_cleared (num_ssa_names);
394 : :
395 : 54210542 : if (!m_ssa_ranges[v])
396 : : {
397 : : // Use sparse bitmap representation if there are too many basic blocks.
398 : 24060934 : if (last_basic_block_for_fn (cfun) > param_vrp_sparse_threshold)
399 : : {
400 : 11280 : void *r = m_range_allocator->alloc (sizeof (sbr_sparse_bitmap));
401 : 11280 : m_ssa_ranges[v] = new (r) sbr_sparse_bitmap (TREE_TYPE (name),
402 : : m_range_allocator,
403 : 11280 : &m_bitmaps);
404 : : }
405 : 24049654 : else if (last_basic_block_for_fn (cfun) < param_vrp_vector_threshold)
406 : : {
407 : : // For small CFGs use the basic vector implemntation.
408 : 21203712 : void *r = m_range_allocator->alloc (sizeof (sbr_vector));
409 : 21203712 : m_ssa_ranges[v] = new (r) sbr_vector (TREE_TYPE (name),
410 : 21203712 : m_range_allocator);
411 : : }
412 : : else
413 : : {
414 : : // Otherwise use the sparse vector implementation.
415 : 2845942 : void *r = m_range_allocator->alloc (sizeof (sbr_lazy_vector));
416 : 2845942 : m_ssa_ranges[v] = new (r) sbr_lazy_vector (TREE_TYPE (name),
417 : : m_range_allocator,
418 : 2845942 : &m_bitmaps);
419 : : }
420 : : }
421 : 54210542 : 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 : 912053053 : block_range_cache::query_block_ranges (tree name)
430 : : {
431 : 912053053 : unsigned v = SSA_NAME_VERSION (name);
432 : 912053053 : 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 : 611289632 : block_range_cache::get_bb_range (vrange &r, tree name, const_basic_block bb)
444 : : {
445 : 611289632 : ssa_block_ranges *ptr = query_block_ranges (name);
446 : 611289632 : if (ptr)
447 : 445802545 : 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 : 300763421 : block_range_cache::bb_range_p (tree name, const_basic_block bb)
455 : : {
456 : 300763421 : ssa_block_ranges *ptr = query_block_ranges (name);
457 : 300763421 : if (ptr)
458 : 217842143 : 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 : 257 : block_range_cache::dump (FILE *f, basic_block bb, bool print_varying)
485 : : {
486 : 257 : unsigned x;
487 : 257 : bool summarize_varying = false;
488 : 13621 : for (x = 1; x < m_ssa_ranges.length (); ++x)
489 : : {
490 : 13364 : if (!m_ssa_ranges[x])
491 : 24165 : continue;
492 : :
493 : 1316 : if (!gimple_range_ssa_p (ssa_name (x)))
494 : 69 : continue;
495 : :
496 : 1247 : value_range r (TREE_TYPE (ssa_name (x)));
497 : 1247 : if (m_ssa_ranges[x]->get_bb_range (r, bb))
498 : : {
499 : 217 : if (!print_varying && r.varying_p ())
500 : : {
501 : 0 : summarize_varying = true;
502 : 0 : continue;
503 : : }
504 : 217 : print_generic_expr (f, ssa_name (x), TDF_NONE);
505 : 217 : fprintf (f, "\t");
506 : 217 : r.dump(f);
507 : 217 : fprintf (f, "\n");
508 : : }
509 : 1247 : }
510 : : // If there were any varying entries, lump them all together.
511 : 257 : 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 : 257 : }
535 : :
536 : : // -------------------------------------------------------------------------
537 : :
538 : : // Initialize an ssa cache.
539 : :
540 : 49027581 : ssa_cache::ssa_cache ()
541 : : {
542 : 49027581 : m_tab.create (0);
543 : 49027581 : m_range_allocator = new vrange_allocator;
544 : 49027581 : }
545 : :
546 : : // Deconstruct an ssa cache.
547 : :
548 : 49027572 : ssa_cache::~ssa_cache ()
549 : : {
550 : 49027572 : m_tab.release ();
551 : 49027572 : delete m_range_allocator;
552 : 49027572 : }
553 : :
554 : : // Enable a query to evaluate staements/ramnges based on picking up ranges
555 : : // from just an ssa-cache.
556 : :
557 : : bool
558 : 1684985 : ssa_cache::range_of_expr (vrange &r, tree expr, gimple *stmt)
559 : : {
560 : 1684985 : if (!gimple_range_ssa_p (expr))
561 : 1384398 : return get_tree_range (r, expr, stmt);
562 : :
563 : 300587 : if (!get_range (r, expr))
564 : 3338 : 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 : 232 : ssa_cache::has_range (tree name) const
572 : : {
573 : 232 : unsigned v = SSA_NAME_VERSION (name);
574 : 232 : if (v >= m_tab.length ())
575 : : return false;
576 : 226 : 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 : 983563410 : ssa_cache::get_range (vrange &r, tree name) const
584 : : {
585 : 983563410 : unsigned v = SSA_NAME_VERSION (name);
586 : 983563410 : if (v >= m_tab.length ())
587 : : return false;
588 : :
589 : 973644349 : vrange_storage *stow = m_tab[v];
590 : 973644349 : if (!stow)
591 : : return false;
592 : 796846473 : stow->get_vrange (r, TREE_TYPE (name));
593 : 796846473 : 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 : 132970487 : ssa_cache::set_range (tree name, const vrange &r)
601 : : {
602 : 132970487 : unsigned v = SSA_NAME_VERSION (name);
603 : 132970487 : if (v >= m_tab.length ())
604 : 13886056 : m_tab.safe_grow_cleared (num_ssa_names + 1);
605 : :
606 : 132970487 : vrange_storage *m = m_tab[v];
607 : 132970487 : if (m && m->fits_p (r))
608 : 17807162 : m->set_vrange (r);
609 : : else
610 : 115163325 : m_tab[v] = m_range_allocator->clone (r);
611 : 132970487 : 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 : 123 : ssa_cache::merge_range (tree name, const vrange &r)
619 : : {
620 : 123 : unsigned v = SSA_NAME_VERSION (name);
621 : 123 : if (v >= m_tab.length ())
622 : 12 : m_tab.safe_grow_cleared (num_ssa_names + 1);
623 : :
624 : 123 : vrange_storage *m = m_tab[v];
625 : : // Check if this is a new value.
626 : 123 : if (!m)
627 : 121 : m_tab[v] = m_range_allocator->clone (r);
628 : : else
629 : : {
630 : 2 : value_range curr (TREE_TYPE (name));
631 : 2 : m->get_vrange (curr, TREE_TYPE (name));
632 : : // If there is no change, return false.
633 : 2 : if (!curr.intersect (r))
634 : 2 : 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 : 2 : }
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 : 69 : ssa_cache::dump (FILE *f)
668 : : {
669 : 3543 : for (unsigned x = 1; x < num_ssa_names; x++)
670 : : {
671 : 3474 : if (!gimple_range_ssa_p (ssa_name (x)))
672 : 1312 : continue;
673 : 2162 : value_range r (TREE_TYPE (ssa_name (x)));
674 : : // Dump all non-varying ranges.
675 : 2162 : if (get_range (r, ssa_name (x)) && !r.varying_p ())
676 : : {
677 : 317 : print_generic_expr (f, ssa_name (x), TDF_NONE);
678 : 317 : fprintf (f, " : ");
679 : 317 : r.dump (f);
680 : 317 : fprintf (f, "\n");
681 : : }
682 : 2162 : }
683 : :
684 : 69 : }
685 : :
686 : : // Construct an ssa_lazy_cache. If OB is specified, us it, otherwise use
687 : : // a local bitmap obstack.
688 : :
689 : 24453924 : ssa_lazy_cache::ssa_lazy_cache (bitmap_obstack *ob)
690 : : {
691 : 24453924 : if (!ob)
692 : : {
693 : 24453915 : bitmap_obstack_initialize (&m_bitmaps);
694 : 24453915 : m_ob = &m_bitmaps;
695 : : }
696 : : else
697 : 9 : m_ob = ob;
698 : 24453924 : active_p = BITMAP_ALLOC (m_ob);
699 : 24453924 : }
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 : 24453915 : ssa_lazy_cache::~ssa_lazy_cache ()
705 : : {
706 : 24453915 : if (m_ob == &m_bitmaps)
707 : 24453915 : bitmap_obstack_release (&m_bitmaps);
708 : : else
709 : 0 : BITMAP_FREE (active_p);
710 : 24453915 : }
711 : :
712 : : // Return true if NAME has an active range in the cache.
713 : :
714 : : bool
715 : 275 : ssa_lazy_cache::has_range (tree name) const
716 : : {
717 : 275 : 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 : 87979158 : ssa_lazy_cache::set_range (tree name, const vrange &r)
725 : : {
726 : 87979158 : unsigned v = SSA_NAME_VERSION (name);
727 : 87979158 : if (!bitmap_set_bit (active_p, v))
728 : : {
729 : : // There is already an entry, simply set it.
730 : 10484380 : gcc_checking_assert (v < m_tab.length ());
731 : 10484380 : return ssa_cache::set_range (name, r);
732 : : }
733 : 77494778 : if (v >= m_tab.length ())
734 : 41030702 : m_tab.safe_grow (num_ssa_names + 1);
735 : 77494778 : m_tab[v] = m_range_allocator->clone (r);
736 : 77494778 : 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 : 225 : ssa_lazy_cache::merge_range (tree name, const vrange &r)
744 : : {
745 : 225 : unsigned v = SSA_NAME_VERSION (name);
746 : 225 : if (!bitmap_set_bit (active_p, v))
747 : : {
748 : : // There is already an entry, simply merge it.
749 : 2 : gcc_checking_assert (v < m_tab.length ());
750 : 2 : return ssa_cache::merge_range (name, r);
751 : : }
752 : 223 : if (v >= m_tab.length ())
753 : 156 : m_tab.safe_grow (num_ssa_names + 1);
754 : 223 : m_tab[v] = m_range_allocator->clone (r);
755 : 223 : 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 : 9 : ssa_lazy_cache::merge (const ssa_lazy_cache &cache)
764 : : {
765 : 9 : unsigned x;
766 : 9 : bitmap_iterator bi;
767 : 74 : EXECUTE_IF_SET_IN_BITMAP (cache.active_p, 0, x, bi)
768 : : {
769 : 65 : tree name = ssa_name (x);
770 : 65 : value_range r(TREE_TYPE (name));
771 : 65 : cache.get_range (r, name);
772 : 65 : merge_range (ssa_name (x), r);
773 : 65 : }
774 : 9 : }
775 : :
776 : : // Return TRUE if NAME has a range, and return it in R.
777 : :
778 : : bool
779 : 224987607 : ssa_lazy_cache::get_range (vrange &r, tree name) const
780 : : {
781 : 224987607 : if (!bitmap_bit_p (active_p, SSA_NAME_VERSION (name)))
782 : : return false;
783 : 93713691 : return ssa_cache::get_range (r, name);
784 : : }
785 : :
786 : : // Remove NAME from the active range list.
787 : :
788 : : void
789 : 45173315 : ssa_lazy_cache::clear_range (tree name)
790 : : {
791 : 45173315 : bitmap_clear_bit (active_p, SSA_NAME_VERSION (name));
792 : 45173315 : }
793 : :
794 : : // Remove all ranges from the active range list.
795 : :
796 : : void
797 : 29984824 : ssa_lazy_cache::clear ()
798 : : {
799 : 29984824 : bitmap_clear (active_p);
800 : 29984824 : }
801 : :
802 : : // --------------------------------------------------------------------------
803 : :
804 : :
805 : : // This class will manage the timestamps for each ssa_name.
806 : : // When a value is calculated, the timestamp is set to the current time.
807 : : // Current time is then incremented. Any dependencies will already have
808 : : // been calculated, and will thus have older timestamps.
809 : : // If one of those values is ever calculated again, it will get a newer
810 : : // timestamp, and the "current_p" check will fail.
811 : :
812 : : class temporal_cache
813 : : {
814 : : public:
815 : : temporal_cache ();
816 : : ~temporal_cache ();
817 : : bool current_p (tree name, tree dep1, tree dep2) const;
818 : : void set_timestamp (tree name);
819 : : void set_always_current (tree name, bool value);
820 : : bool always_current_p (tree name) const;
821 : : private:
822 : : int temporal_value (unsigned ssa) const;
823 : : int m_current_time;
824 : : vec <int> m_timestamp;
825 : : };
826 : :
827 : : inline
828 : 24573651 : temporal_cache::temporal_cache ()
829 : : {
830 : 24573651 : m_current_time = 1;
831 : 24573651 : m_timestamp.create (0);
832 : 49147302 : m_timestamp.safe_grow_cleared (num_ssa_names);
833 : 24573651 : }
834 : :
835 : : inline
836 : 24573651 : temporal_cache::~temporal_cache ()
837 : : {
838 : 24573651 : m_timestamp.release ();
839 : 24573651 : }
840 : :
841 : : // Return the timestamp value for SSA, or 0 if there isn't one.
842 : :
843 : : inline int
844 : 490895729 : temporal_cache::temporal_value (unsigned ssa) const
845 : : {
846 : 490895729 : if (ssa >= m_timestamp.length ())
847 : : return 0;
848 : 490895729 : return abs (m_timestamp[ssa]);
849 : : }
850 : :
851 : : // Return TRUE if the timestamp for NAME is newer than any of its dependents.
852 : : // Up to 2 dependencies can be checked.
853 : :
854 : : bool
855 : 298086383 : temporal_cache::current_p (tree name, tree dep1, tree dep2) const
856 : : {
857 : 298086383 : if (always_current_p (name))
858 : : return true;
859 : :
860 : : // Any non-registered dependencies will have a value of 0 and thus be older.
861 : : // Return true if time is newer than either dependent.
862 : 292334158 : int ts = temporal_value (SSA_NAME_VERSION (name));
863 : 445045355 : if (dep1 && ts < temporal_value (SSA_NAME_VERSION (dep1)))
864 : : return false;
865 : 310760298 : if (dep2 && ts < temporal_value (SSA_NAME_VERSION (dep2)))
866 : 4780549 : return false;
867 : :
868 : : return true;
869 : : }
870 : :
871 : : // This increments the global timer and sets the timestamp for NAME.
872 : :
873 : : inline void
874 : 34406176 : temporal_cache::set_timestamp (tree name)
875 : : {
876 : 34406176 : unsigned v = SSA_NAME_VERSION (name);
877 : 34406176 : if (v >= m_timestamp.length ())
878 : 0 : m_timestamp.safe_grow_cleared (num_ssa_names + 20);
879 : 34406176 : m_timestamp[v] = ++m_current_time;
880 : 34406176 : }
881 : :
882 : : // Set the timestamp to 0, marking it as "always up to date".
883 : :
884 : : inline void
885 : 240569428 : temporal_cache::set_always_current (tree name, bool value)
886 : : {
887 : 240569428 : unsigned v = SSA_NAME_VERSION (name);
888 : 240569428 : if (v >= m_timestamp.length ())
889 : 900 : m_timestamp.safe_grow_cleared (num_ssa_names + 20);
890 : :
891 : 240569428 : int ts = abs (m_timestamp[v]);
892 : : // If this does not have a timestamp, create one.
893 : 240569428 : if (ts == 0)
894 : 111956089 : ts = ++m_current_time;
895 : 240569428 : m_timestamp[v] = value ? -ts : ts;
896 : 240569428 : }
897 : :
898 : : // Return true if NAME is always current.
899 : :
900 : : inline bool
901 : 298086383 : temporal_cache::always_current_p (tree name) const
902 : : {
903 : 298086383 : unsigned v = SSA_NAME_VERSION (name);
904 : 298086383 : if (v >= m_timestamp.length ())
905 : : return false;
906 : 298086383 : return m_timestamp[v] <= 0;
907 : : }
908 : :
909 : : // --------------------------------------------------------------------------
910 : :
911 : : // This class provides an abstraction of a list of blocks to be updated
912 : : // by the cache. It is currently a stack but could be changed. It also
913 : : // maintains a list of blocks which have failed propagation, and does not
914 : : // enter any of those blocks into the list.
915 : :
916 : : // A vector over the BBs is maintained, and an entry of 0 means it is not in
917 : : // a list. Otherwise, the entry is the next block in the list. -1 terminates
918 : : // the list. m_head points to the top of the list, -1 if the list is empty.
919 : :
920 : : class update_list
921 : : {
922 : : public:
923 : : update_list ();
924 : : ~update_list ();
925 : : void add (basic_block bb);
926 : : basic_block pop ();
927 : 112886817 : inline bool empty_p () { return m_update_head == -1; }
928 : 3747198 : inline void clear_failures () { bitmap_clear (m_propfail); }
929 : 6 : inline void propagation_failed (basic_block bb)
930 : 6 : { bitmap_set_bit (m_propfail, bb->index); }
931 : : private:
932 : : vec<int> m_update_list;
933 : : int m_update_head;
934 : : bitmap m_propfail;
935 : : bitmap_obstack m_bitmaps;
936 : : };
937 : :
938 : : // Create an update list.
939 : :
940 : 24573651 : update_list::update_list ()
941 : : {
942 : 24573651 : m_update_list.create (0);
943 : 24573651 : m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun) + 64);
944 : 24573651 : m_update_head = -1;
945 : 24573651 : bitmap_obstack_initialize (&m_bitmaps);
946 : 24573651 : m_propfail = BITMAP_ALLOC (&m_bitmaps);
947 : 24573651 : }
948 : :
949 : : // Destroy an update list.
950 : :
951 : 24573651 : update_list::~update_list ()
952 : : {
953 : 24573651 : m_update_list.release ();
954 : 24573651 : bitmap_obstack_release (&m_bitmaps);
955 : 24573651 : }
956 : :
957 : : // Add BB to the list of blocks to update, unless it's already in the list.
958 : :
959 : : void
960 : 4065671 : update_list::add (basic_block bb)
961 : : {
962 : 4065671 : int i = bb->index;
963 : : // If propagation has failed for BB, or its already in the list, don't
964 : : // add it again.
965 : 4065671 : if ((unsigned)i >= m_update_list.length ())
966 : 0 : m_update_list.safe_grow_cleared (i + 64);
967 : 4065671 : if (!m_update_list[i] && !bitmap_bit_p (m_propfail, i))
968 : : {
969 : 4044203 : if (empty_p ())
970 : : {
971 : 3896938 : m_update_head = i;
972 : 3896938 : m_update_list[i] = -1;
973 : : }
974 : : else
975 : : {
976 : 147265 : gcc_checking_assert (m_update_head > 0);
977 : 147265 : m_update_list[i] = m_update_head;
978 : 147265 : m_update_head = i;
979 : : }
980 : : }
981 : 4065671 : }
982 : :
983 : : // Remove a block from the list.
984 : :
985 : : basic_block
986 : 4044203 : update_list::pop ()
987 : : {
988 : 4044203 : gcc_checking_assert (!empty_p ());
989 : 4044203 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, m_update_head);
990 : 4044203 : int pop = m_update_head;
991 : 4044203 : m_update_head = m_update_list[pop];
992 : 4044203 : m_update_list[pop] = 0;
993 : 4044203 : return bb;
994 : : }
995 : :
996 : : // --------------------------------------------------------------------------
997 : :
998 : 24573651 : ranger_cache::ranger_cache (int not_executable_flag, bool use_imm_uses)
999 : : {
1000 : 24573651 : m_workback = vNULL;
1001 : 24573651 : m_temporal = new temporal_cache;
1002 : :
1003 : : // If DOM info is available, spawn an oracle as well.
1004 : 24573651 : create_relation_oracle ();
1005 : : // Create an infer oracle using this cache as the range query. The cache
1006 : : // version acts as a read-only query, and will spawn no additional lookups.
1007 : : // It just ues what is already known.
1008 : 24573651 : create_infer_oracle (this, use_imm_uses);
1009 : 24573651 : create_gori (not_executable_flag, param_vrp_switch_limit);
1010 : :
1011 : 24573651 : unsigned x, lim = last_basic_block_for_fn (cfun);
1012 : : // Calculate outgoing range info upfront. This will fully populate the
1013 : : // m_maybe_variant bitmap which will help eliminate processing of names
1014 : : // which never have their ranges adjusted.
1015 : 302209619 : for (x = 0; x < lim ; x++)
1016 : : {
1017 : 277635968 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, x);
1018 : 277635968 : if (bb)
1019 : 261983628 : gori_ssa ()->exports (bb);
1020 : : }
1021 : 24573651 : m_update = new update_list ();
1022 : 24573651 : }
1023 : :
1024 : 24573651 : ranger_cache::~ranger_cache ()
1025 : : {
1026 : 24573651 : delete m_update;
1027 : 24573651 : destroy_infer_oracle ();
1028 : 24573651 : destroy_relation_oracle ();
1029 : 49147302 : delete m_temporal;
1030 : 24573651 : m_workback.release ();
1031 : 24573651 : }
1032 : :
1033 : : // Dump the global caches to file F. if GORI_DUMP is true, dump the
1034 : : // gori map as well.
1035 : :
1036 : : void
1037 : 46 : ranger_cache::dump (FILE *f)
1038 : : {
1039 : 46 : fprintf (f, "Non-varying global ranges:\n");
1040 : 46 : fprintf (f, "=========================:\n");
1041 : 46 : m_globals.dump (f);
1042 : 46 : fprintf (f, "\n");
1043 : 46 : }
1044 : :
1045 : : // Dump the caches for basic block BB to file F.
1046 : :
1047 : : void
1048 : 257 : ranger_cache::dump_bb (FILE *f, basic_block bb)
1049 : : {
1050 : 257 : gori_ssa ()->dump (f, bb, false);
1051 : 257 : m_on_entry.dump (f, bb);
1052 : 257 : m_relation->dump (f, bb);
1053 : 257 : }
1054 : :
1055 : : // Get the global range for NAME, and return in R. Return false if the
1056 : : // global range is not set, and return the legacy global value in R.
1057 : :
1058 : : bool
1059 : 716871912 : ranger_cache::get_global_range (vrange &r, tree name) const
1060 : : {
1061 : 716871912 : if (m_globals.get_range (r, name))
1062 : : return true;
1063 : 166737508 : gimple_range_global (r, name);
1064 : 166737508 : return false;
1065 : : }
1066 : :
1067 : : // Get the global range for NAME, and return in R. Return false if the
1068 : : // global range is not set, and R will contain the legacy global value.
1069 : : // CURRENT_P is set to true if the value was in cache and not stale.
1070 : : // Otherwise, set CURRENT_P to false and mark as it always current.
1071 : : // If the global cache did not have a value, initialize it as well.
1072 : : // After this call, the global cache will have a value.
1073 : :
1074 : : bool
1075 : 300442825 : ranger_cache::get_global_range (vrange &r, tree name, bool ¤t_p)
1076 : : {
1077 : 300442825 : bool had_global = get_global_range (r, name);
1078 : :
1079 : : // If there was a global value, set current flag, otherwise set a value.
1080 : 300442825 : current_p = false;
1081 : 300442825 : if (had_global)
1082 : 376973472 : current_p = r.singleton_p ()
1083 : 376818423 : || m_temporal->current_p (name, gori_ssa ()->depend1 (name),
1084 : 188331687 : gori_ssa ()->depend2 (name));
1085 : : else
1086 : : {
1087 : : // If no global value has been set and value is VARYING, fold the stmt
1088 : : // using just global ranges to get a better initial value.
1089 : : // After inlining we tend to decide some things are constant, so
1090 : : // so not do this evaluation after inlining.
1091 : 111956089 : if (r.varying_p () && !cfun->after_inlining)
1092 : : {
1093 : 19300105 : gimple *s = SSA_NAME_DEF_STMT (name);
1094 : : // Do not process PHIs as SCEV may be in use and it can
1095 : : // spawn cyclic lookups.
1096 : 19300105 : if (gimple_get_lhs (s) == name && !is_a<gphi *> (s))
1097 : : {
1098 : 15055984 : if (!fold_range (r, s, get_global_range_query ()))
1099 : 0 : gimple_range_global (r, name);
1100 : : }
1101 : : }
1102 : 111956089 : m_globals.set_range (name, r);
1103 : : }
1104 : :
1105 : : // If the existing value was not current, mark it as always current.
1106 : 300442825 : if (!current_p)
1107 : 120284714 : m_temporal->set_always_current (name, true);
1108 : 300442825 : return had_global;
1109 : : }
1110 : :
1111 : : // Set the global range of NAME to R and give it a timestamp.
1112 : :
1113 : : void
1114 : 120284714 : ranger_cache::set_global_range (tree name, const vrange &r, bool changed)
1115 : : {
1116 : : // Setting a range always clears the always_current flag.
1117 : 120284714 : m_temporal->set_always_current (name, false);
1118 : 120284714 : if (!changed)
1119 : : {
1120 : : // If there are dependencies, make sure this is not out of date.
1121 : 109754696 : if (!m_temporal->current_p (name, gori_ssa ()->depend1 (name),
1122 : 109754696 : gori_ssa ()->depend2 (name)))
1123 : 23876158 : m_temporal->set_timestamp (name);
1124 : 109754696 : return;
1125 : : }
1126 : 10530018 : if (m_globals.set_range (name, r))
1127 : : {
1128 : : // If there was already a range set, propagate the new value.
1129 : 10530018 : basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1130 : 10530018 : if (!bb)
1131 : 0 : bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1132 : :
1133 : 10530018 : if (DEBUG_RANGE_CACHE)
1134 : 0 : fprintf (dump_file, " GLOBAL :");
1135 : :
1136 : 10530018 : propagate_updated_value (name, bb);
1137 : : }
1138 : : // Constants no longer need to tracked. Any further refinement has to be
1139 : : // undefined. Propagation works better with constants. PR 100512.
1140 : : // Pointers which resolve to non-zero also do not need
1141 : : // tracking in the cache as they will never change. See PR 98866.
1142 : : // Timestamp must always be updated, or dependent calculations may
1143 : : // not include this latest value. PR 100774.
1144 : :
1145 : 10530018 : if (r.singleton_p ()
1146 : 10530018 : || (POINTER_TYPE_P (TREE_TYPE (name)) && r.nonzero_p ()))
1147 : 1990477 : gori_ssa ()->set_range_invariant (name);
1148 : 10530018 : m_temporal->set_timestamp (name);
1149 : : }
1150 : :
1151 : : // Provide lookup for the gori-computes class to access the best known range
1152 : : // of an ssa_name in any given basic block. Note, this does no additional
1153 : : // lookups, just accesses the data that is already known.
1154 : :
1155 : : // Get the range of NAME when the def occurs in block BB. If BB is NULL
1156 : : // get the best global value available.
1157 : :
1158 : : void
1159 : 172676762 : ranger_cache::range_of_def (vrange &r, tree name, basic_block bb)
1160 : : {
1161 : 172676762 : gcc_checking_assert (gimple_range_ssa_p (name));
1162 : 293264809 : gcc_checking_assert (!bb || bb == gimple_bb (SSA_NAME_DEF_STMT (name)));
1163 : :
1164 : : // Pick up the best global range available.
1165 : 172676762 : if (!m_globals.get_range (r, name))
1166 : : {
1167 : : // If that fails, try to calculate the range using just global values.
1168 : 19976090 : gimple *s = SSA_NAME_DEF_STMT (name);
1169 : 19976090 : if (gimple_get_lhs (s) == name)
1170 : 17412789 : fold_range (r, s, get_global_range_query ());
1171 : : else
1172 : 2563301 : gimple_range_global (r, name);
1173 : : }
1174 : 172676762 : }
1175 : :
1176 : : // Get the range of NAME as it occurs on entry to block BB. Use MODE for
1177 : : // lookups.
1178 : :
1179 : : void
1180 : 107981931 : ranger_cache::entry_range (vrange &r, tree name, basic_block bb,
1181 : : enum rfd_mode mode)
1182 : : {
1183 : 107981931 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1184 : : {
1185 : 0 : gimple_range_global (r, name);
1186 : 0 : return;
1187 : : }
1188 : :
1189 : : // If NAME is invariant, simply return the defining range.
1190 : 107981931 : if (!gori ().has_edge_range_p (name))
1191 : : {
1192 : 29506997 : range_of_def (r, name);
1193 : 29506997 : return;
1194 : : }
1195 : :
1196 : : // Look for the on-entry value of name in BB from the cache.
1197 : : // Otherwise pick up the best available global value.
1198 : 78474934 : if (!m_on_entry.get_bb_range (r, name, bb))
1199 : 27185285 : if (!range_from_dom (r, name, bb, mode))
1200 : 22581718 : range_of_def (r, name);
1201 : : }
1202 : :
1203 : : // Get the range of NAME as it occurs on exit from block BB. Use MODE for
1204 : : // lookups.
1205 : :
1206 : : void
1207 : 82995090 : ranger_cache::exit_range (vrange &r, tree name, basic_block bb,
1208 : : enum rfd_mode mode)
1209 : : {
1210 : 82995090 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1211 : : {
1212 : 10292 : gimple_range_global (r, name);
1213 : 10292 : return;
1214 : : }
1215 : :
1216 : 82984798 : gimple *s = SSA_NAME_DEF_STMT (name);
1217 : 82984798 : basic_block def_bb = gimple_bb (s);
1218 : 82984798 : if (def_bb == bb)
1219 : 39791800 : range_of_def (r, name, bb);
1220 : : else
1221 : 43192998 : entry_range (r, name, bb, mode);
1222 : : }
1223 : :
1224 : : // Get the range of NAME on edge E using MODE, return the result in R.
1225 : : // Always returns a range and true.
1226 : :
1227 : : bool
1228 : 73609963 : ranger_cache::edge_range (vrange &r, edge e, tree name, enum rfd_mode mode)
1229 : : {
1230 : 73609963 : exit_range (r, name, e->src, mode);
1231 : : // If this is not an abnormal edge, check for inferred ranges on exit.
1232 : 73609963 : if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
1233 : 73269422 : infer_oracle ().maybe_adjust_range (r, name, e->src);
1234 : 73609963 : value_range er (TREE_TYPE (name));
1235 : 73609963 : if (gori ().edge_range_p (er, e, name, *this))
1236 : 16121526 : r.intersect (er);
1237 : 147219926 : return true;
1238 : 73609963 : }
1239 : :
1240 : :
1241 : :
1242 : : // Implement range_of_expr.
1243 : :
1244 : : bool
1245 : 176588682 : ranger_cache::range_of_expr (vrange &r, tree name, gimple *stmt)
1246 : : {
1247 : 176588682 : if (!gimple_range_ssa_p (name))
1248 : : {
1249 : 31003502 : get_tree_range (r, name, stmt);
1250 : 31003502 : return true;
1251 : : }
1252 : :
1253 : 145585180 : basic_block bb = gimple_bb (stmt);
1254 : 145585180 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1255 : 145585180 : basic_block def_bb = gimple_bb (def_stmt);
1256 : :
1257 : 145585180 : if (bb == def_bb)
1258 : 80796247 : range_of_def (r, name, bb);
1259 : : else
1260 : 64788933 : entry_range (r, name, bb, RFD_NONE);
1261 : : return true;
1262 : : }
1263 : :
1264 : :
1265 : : // Implement range_on_edge. Always return the best available range using
1266 : : // the current cache values.
1267 : :
1268 : : bool
1269 : 63525109 : ranger_cache::range_on_edge (vrange &r, edge e, tree expr)
1270 : : {
1271 : 63525109 : if (gimple_range_ssa_p (expr))
1272 : 61152006 : return edge_range (r, e, expr, RFD_NONE);
1273 : 2373103 : return get_tree_range (r, expr, NULL);
1274 : : }
1275 : :
1276 : : // Return a static range for NAME on entry to basic block BB in R. If
1277 : : // calc is true, fill any cache entries required between BB and the
1278 : : // def block for NAME. Otherwise, return false if the cache is empty.
1279 : :
1280 : : bool
1281 : 339663654 : ranger_cache::block_range (vrange &r, basic_block bb, tree name, bool calc)
1282 : : {
1283 : 339663654 : gcc_checking_assert (gimple_range_ssa_p (name));
1284 : :
1285 : : // If there are no range calculations anywhere in the IL, global range
1286 : : // applies everywhere, so don't bother caching it.
1287 : 339663654 : if (!gori ().has_edge_range_p (name))
1288 : : return false;
1289 : :
1290 : 208558591 : if (calc)
1291 : : {
1292 : 99919559 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1293 : 99919559 : basic_block def_bb = NULL;
1294 : 99919559 : if (def_stmt)
1295 : 99919559 : def_bb = gimple_bb (def_stmt);
1296 : 99919559 : if (!def_bb)
1297 : : {
1298 : : // If we get to the entry block, this better be a default def
1299 : : // or range_on_entry was called for a block not dominated by
1300 : : // the def. But it could be also SSA_NAME defined by a statement
1301 : : // not yet in the IL (such as queued edge insertion), in that case
1302 : : // just punt.
1303 : 15368676 : if (!SSA_NAME_IS_DEFAULT_DEF (name))
1304 : : return false;
1305 : 15368675 : def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1306 : : }
1307 : :
1308 : : // There is no range on entry for the definition block.
1309 : 99919558 : if (def_bb == bb)
1310 : : return false;
1311 : :
1312 : : // Otherwise, go figure out what is known in predecessor blocks.
1313 : 99574684 : fill_block_cache (name, bb, def_bb);
1314 : 99574684 : gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
1315 : : }
1316 : 208213716 : return m_on_entry.get_bb_range (r, name, bb);
1317 : : }
1318 : :
1319 : : // If there is anything in the propagation update_list, continue
1320 : : // processing NAME until the list of blocks is empty.
1321 : :
1322 : : void
1323 : 3747198 : ranger_cache::propagate_cache (tree name)
1324 : : {
1325 : 3747198 : basic_block bb;
1326 : 3747198 : edge_iterator ei;
1327 : 3747198 : edge e;
1328 : 3747198 : tree type = TREE_TYPE (name);
1329 : 3747198 : value_range new_range (type);
1330 : 3747198 : value_range current_range (type);
1331 : 3747198 : value_range e_range (type);
1332 : :
1333 : : // Process each block by seeing if its calculated range on entry is
1334 : : // the same as its cached value. If there is a difference, update
1335 : : // the cache to reflect the new value, and check to see if any
1336 : : // successors have cache entries which may need to be checked for
1337 : : // updates.
1338 : :
1339 : 11538599 : while (!m_update->empty_p ())
1340 : : {
1341 : 4044203 : bb = m_update->pop ();
1342 : 4044203 : gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
1343 : 4044203 : m_on_entry.get_bb_range (current_range, name, bb);
1344 : :
1345 : 4044203 : if (DEBUG_RANGE_CACHE)
1346 : : {
1347 : 0 : fprintf (dump_file, "FWD visiting block %d for ", bb->index);
1348 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1349 : 0 : fprintf (dump_file, " starting range : ");
1350 : 0 : current_range.dump (dump_file);
1351 : 0 : fprintf (dump_file, "\n");
1352 : : }
1353 : :
1354 : : // Calculate the "new" range on entry by unioning the pred edges.
1355 : 4044203 : new_range.set_undefined ();
1356 : 7908260 : FOR_EACH_EDGE (e, ei, bb->preds)
1357 : : {
1358 : 4520345 : edge_range (e_range, e, name, RFD_READ_ONLY);
1359 : 4520345 : if (DEBUG_RANGE_CACHE)
1360 : : {
1361 : 0 : fprintf (dump_file, " edge %d->%d :", e->src->index, bb->index);
1362 : 0 : e_range.dump (dump_file);
1363 : 0 : fprintf (dump_file, "\n");
1364 : : }
1365 : 4520345 : new_range.union_ (e_range);
1366 : 4520345 : if (new_range.varying_p ())
1367 : : break;
1368 : : }
1369 : :
1370 : : // If the range on entry has changed, update it.
1371 : 4044203 : if (new_range != current_range)
1372 : : {
1373 : 1373707 : bool ok_p = m_on_entry.set_bb_range (name, bb, new_range);
1374 : : // If the cache couldn't set the value, mark it as failed.
1375 : 1373707 : if (!ok_p)
1376 : 6 : m_update->propagation_failed (bb);
1377 : 1373707 : if (DEBUG_RANGE_CACHE)
1378 : : {
1379 : 0 : if (!ok_p)
1380 : : {
1381 : 0 : fprintf (dump_file, " Cache failure to store value:");
1382 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1383 : 0 : fprintf (dump_file, " ");
1384 : : }
1385 : : else
1386 : : {
1387 : 0 : fprintf (dump_file, " Updating range to ");
1388 : 0 : new_range.dump (dump_file);
1389 : : }
1390 : 0 : fprintf (dump_file, "\n Updating blocks :");
1391 : : }
1392 : : // Mark each successor that has a range to re-check its range
1393 : 3265872 : FOR_EACH_EDGE (e, ei, bb->succs)
1394 : 1892165 : if (m_on_entry.bb_range_p (name, e->dest))
1395 : : {
1396 : 260030 : if (DEBUG_RANGE_CACHE)
1397 : 0 : fprintf (dump_file, " bb%d",e->dest->index);
1398 : 260030 : m_update->add (e->dest);
1399 : : }
1400 : 1373707 : if (DEBUG_RANGE_CACHE)
1401 : 0 : fprintf (dump_file, "\n");
1402 : : }
1403 : : }
1404 : 3747198 : if (DEBUG_RANGE_CACHE)
1405 : : {
1406 : 0 : fprintf (dump_file, "DONE visiting blocks for ");
1407 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1408 : 0 : fprintf (dump_file, "\n");
1409 : : }
1410 : 3747198 : m_update->clear_failures ();
1411 : 3747198 : }
1412 : :
1413 : : // Check to see if an update to the value for NAME in BB has any effect
1414 : : // on values already in the on-entry cache for successor blocks.
1415 : : // If it does, update them. Don't visit any blocks which don't have a cache
1416 : : // entry.
1417 : :
1418 : : void
1419 : 48473664 : ranger_cache::propagate_updated_value (tree name, basic_block bb)
1420 : : {
1421 : 48473664 : edge e;
1422 : 48473664 : edge_iterator ei;
1423 : :
1424 : : // The update work list should be empty at this point.
1425 : 48473664 : gcc_checking_assert (m_update->empty_p ());
1426 : 48473664 : gcc_checking_assert (bb);
1427 : :
1428 : 48473664 : if (DEBUG_RANGE_CACHE)
1429 : : {
1430 : 0 : fprintf (dump_file, " UPDATE cache for ");
1431 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1432 : 0 : fprintf (dump_file, " in BB %d : successors : ", bb->index);
1433 : : }
1434 : 140515783 : FOR_EACH_EDGE (e, ei, bb->succs)
1435 : : {
1436 : : // Only update active cache entries.
1437 : 92042119 : if (m_on_entry.bb_range_p (name, e->dest))
1438 : : {
1439 : 3721394 : m_update->add (e->dest);
1440 : 3721394 : if (DEBUG_RANGE_CACHE)
1441 : 0 : fprintf (dump_file, " UPDATE: bb%d", e->dest->index);
1442 : : }
1443 : : }
1444 : 48473664 : if (!m_update->empty_p ())
1445 : : {
1446 : 3687516 : if (DEBUG_RANGE_CACHE)
1447 : 0 : fprintf (dump_file, "\n");
1448 : 3687516 : propagate_cache (name);
1449 : : }
1450 : : else
1451 : : {
1452 : 44786148 : if (DEBUG_RANGE_CACHE)
1453 : 0 : fprintf (dump_file, " : No updates!\n");
1454 : : }
1455 : 48473664 : }
1456 : :
1457 : : // Make sure that the range-on-entry cache for NAME is set for block BB.
1458 : : // Work back through the CFG to DEF_BB ensuring the range is calculated
1459 : : // on the block/edges leading back to that point.
1460 : :
1461 : : void
1462 : 99574684 : ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
1463 : : {
1464 : 99574684 : edge_iterator ei;
1465 : 99574684 : edge e;
1466 : 99574684 : tree type = TREE_TYPE (name);
1467 : 99574684 : value_range block_result (type);
1468 : 99574684 : value_range undefined (type);
1469 : :
1470 : : // At this point we shouldn't be looking at the def, entry block.
1471 : 99574684 : gcc_checking_assert (bb != def_bb && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
1472 : 99574684 : unsigned start_length = m_workback.length ();
1473 : :
1474 : : // If the block cache is set, then we've already visited this block.
1475 : 99574684 : if (m_on_entry.bb_range_p (name, bb))
1476 : : return;
1477 : :
1478 : 43826191 : if (DEBUG_RANGE_CACHE)
1479 : : {
1480 : 0 : fprintf (dump_file, "\n");
1481 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1482 : 0 : fprintf (dump_file, " : ");
1483 : : }
1484 : :
1485 : : // Check if a dominators can supply the range.
1486 : 43826191 : if (range_from_dom (block_result, name, bb, RFD_FILL))
1487 : : {
1488 : 43766509 : if (DEBUG_RANGE_CACHE)
1489 : : {
1490 : 0 : fprintf (dump_file, "Filled from dominator! : ");
1491 : 0 : block_result.dump (dump_file);
1492 : 0 : fprintf (dump_file, "\n");
1493 : : }
1494 : : // See if any equivalences can refine it.
1495 : : // PR 109462, like 108139 below, a one way equivalence introduced
1496 : : // by a PHI node can also be through the definition side. Disallow it.
1497 : 43766509 : tree equiv_name;
1498 : 43766509 : relation_kind rel;
1499 : 43766509 : int prec = TYPE_PRECISION (type);
1500 : : // If there are too many basic blocks, do not attempt to process
1501 : : // equivalencies.
1502 : 43766509 : if (last_basic_block_for_fn (cfun) > param_vrp_sparse_threshold)
1503 : : {
1504 : 290546 : m_on_entry.set_bb_range (name, bb, block_result);
1505 : 581071 : gcc_checking_assert (m_workback.length () == start_length);
1506 : : return;
1507 : : }
1508 : 51490167 : FOR_EACH_PARTIAL_AND_FULL_EQUIV (m_relation, bb, name, equiv_name, rel)
1509 : : {
1510 : 8014204 : basic_block equiv_bb = gimple_bb (SSA_NAME_DEF_STMT (equiv_name));
1511 : :
1512 : : // Ignore partial equivs that are smaller than this object.
1513 : 14327165 : if (rel != VREL_EQ && prec > pe_to_bits (rel))
1514 : 3064422 : continue;
1515 : :
1516 : : // Check if the equiv has any ranges calculated.
1517 : 7065515 : if (!gori ().has_edge_range_p (equiv_name))
1518 : 293720 : continue;
1519 : :
1520 : : // Check if the equiv definition dominates this block
1521 : 6771795 : if (equiv_bb == bb ||
1522 : 6580075 : (equiv_bb && !dominated_by_p (CDI_DOMINATORS, bb, equiv_bb)))
1523 : 1822013 : continue;
1524 : :
1525 : 4949782 : if (DEBUG_RANGE_CACHE)
1526 : : {
1527 : 0 : if (rel == VREL_EQ)
1528 : 0 : fprintf (dump_file, "Checking Equivalence (");
1529 : : else
1530 : 0 : fprintf (dump_file, "Checking Partial equiv (");
1531 : 0 : print_relation (dump_file, rel);
1532 : 0 : fprintf (dump_file, ") ");
1533 : 0 : print_generic_expr (dump_file, equiv_name, TDF_SLIM);
1534 : 0 : fprintf (dump_file, "\n");
1535 : : }
1536 : 4949782 : value_range equiv_range (TREE_TYPE (equiv_name));
1537 : 4949782 : if (range_from_dom (equiv_range, equiv_name, bb, RFD_READ_ONLY))
1538 : : {
1539 : 4949782 : if (rel != VREL_EQ)
1540 : 3450233 : range_cast (equiv_range, type);
1541 : : else
1542 : 1499549 : adjust_equivalence_range (equiv_range);
1543 : :
1544 : 4949782 : if (block_result.intersect (equiv_range))
1545 : : {
1546 : 97662 : if (DEBUG_RANGE_CACHE)
1547 : : {
1548 : 0 : if (rel == VREL_EQ)
1549 : 0 : fprintf (dump_file, "Equivalence update! : ");
1550 : : else
1551 : 0 : fprintf (dump_file, "Partial equiv update! : ");
1552 : 0 : print_generic_expr (dump_file, equiv_name, TDF_SLIM);
1553 : 0 : fprintf (dump_file, " has range : ");
1554 : 0 : equiv_range.dump (dump_file);
1555 : 0 : fprintf (dump_file, " refining range to :");
1556 : 0 : block_result.dump (dump_file);
1557 : 0 : fprintf (dump_file, "\n");
1558 : : }
1559 : : }
1560 : : }
1561 : 4949782 : }
1562 : :
1563 : 43475963 : m_on_entry.set_bb_range (name, bb, block_result);
1564 : 84046335 : gcc_checking_assert (m_workback.length () == start_length);
1565 : : return;
1566 : : }
1567 : :
1568 : : // Visit each block back to the DEF. Initialize each one to UNDEFINED.
1569 : : // m_visited at the end will contain all the blocks that we needed to set
1570 : : // the range_on_entry cache for.
1571 : 59682 : m_workback.safe_push (bb);
1572 : 59682 : undefined.set_undefined ();
1573 : 59682 : m_on_entry.set_bb_range (name, bb, undefined);
1574 : 59682 : gcc_checking_assert (m_update->empty_p ());
1575 : :
1576 : 261463 : while (m_workback.length () > start_length)
1577 : : {
1578 : 201781 : basic_block node = m_workback.pop ();
1579 : 201781 : if (DEBUG_RANGE_CACHE)
1580 : : {
1581 : 0 : fprintf (dump_file, "BACK visiting block %d for ", node->index);
1582 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1583 : 0 : fprintf (dump_file, "\n");
1584 : : }
1585 : :
1586 : 449882 : FOR_EACH_EDGE (e, ei, node->preds)
1587 : : {
1588 : 248101 : basic_block pred = e->src;
1589 : 248101 : value_range r (TREE_TYPE (name));
1590 : :
1591 : 248101 : if (DEBUG_RANGE_CACHE)
1592 : 0 : fprintf (dump_file, " %d->%d ",e->src->index, e->dest->index);
1593 : :
1594 : : // If the pred block is the def block add this BB to update list.
1595 : 248101 : if (pred == def_bb)
1596 : : {
1597 : 60016 : m_update->add (node);
1598 : 60016 : continue;
1599 : : }
1600 : :
1601 : : // If the pred is entry but NOT def, then it is used before
1602 : : // defined, it'll get set to [] and no need to update it.
1603 : 188085 : if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1604 : : {
1605 : 0 : if (DEBUG_RANGE_CACHE)
1606 : 0 : fprintf (dump_file, "entry: bail.");
1607 : 0 : continue;
1608 : : }
1609 : :
1610 : : // Regardless of whether we have visited pred or not, if the
1611 : : // pred has inferred ranges, revisit this block.
1612 : : // Don't search the DOM tree.
1613 : 188085 : if (infer_oracle ().has_range_p (pred, name))
1614 : : {
1615 : 1341 : if (DEBUG_RANGE_CACHE)
1616 : 0 : fprintf (dump_file, "Inferred range: update ");
1617 : 1341 : m_update->add (node);
1618 : : }
1619 : :
1620 : : // If the pred block already has a range, or if it can contribute
1621 : : // something new. Ie, the edge generates a range of some sort.
1622 : 188085 : if (m_on_entry.get_bb_range (r, name, pred))
1623 : : {
1624 : 45986 : if (DEBUG_RANGE_CACHE)
1625 : : {
1626 : 0 : fprintf (dump_file, "has cache, ");
1627 : 0 : r.dump (dump_file);
1628 : 0 : fprintf (dump_file, ", ");
1629 : : }
1630 : 45986 : if (!r.undefined_p () || gori ().has_edge_range_p (name, e))
1631 : : {
1632 : 22890 : m_update->add (node);
1633 : 22890 : if (DEBUG_RANGE_CACHE)
1634 : 0 : fprintf (dump_file, "update. ");
1635 : : }
1636 : 45986 : continue;
1637 : : }
1638 : :
1639 : 142099 : if (DEBUG_RANGE_CACHE)
1640 : 0 : fprintf (dump_file, "pushing undefined pred block.\n");
1641 : : // If the pred hasn't been visited (has no range), add it to
1642 : : // the list.
1643 : 142099 : gcc_checking_assert (!m_on_entry.bb_range_p (name, pred));
1644 : 142099 : m_on_entry.set_bb_range (name, pred, undefined);
1645 : 142099 : m_workback.safe_push (pred);
1646 : 248101 : }
1647 : : }
1648 : :
1649 : 59682 : if (DEBUG_RANGE_CACHE)
1650 : 0 : fprintf (dump_file, "\n");
1651 : :
1652 : : // Now fill in the marked blocks with values.
1653 : 59682 : propagate_cache (name);
1654 : 59682 : if (DEBUG_RANGE_CACHE)
1655 : 0 : fprintf (dump_file, " Propagation update done.\n");
1656 : 99574684 : }
1657 : :
1658 : : // Resolve the range of BB if the dominators range is R by calculating incoming
1659 : : // edges to this block. All lead back to the dominator so should be cheap.
1660 : : // The range for BB is set and returned in R.
1661 : :
1662 : : void
1663 : 3493467 : ranger_cache::resolve_dom (vrange &r, tree name, basic_block bb)
1664 : : {
1665 : 3493467 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1666 : 3493467 : basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1667 : :
1668 : : // if it doesn't already have a value, store the incoming range.
1669 : 3493467 : if (!m_on_entry.bb_range_p (name, dom_bb) && def_bb != dom_bb)
1670 : : {
1671 : : // If the range can't be store, don't try to accumulate
1672 : : // the range in PREV_BB due to excessive recalculations.
1673 : 865359 : if (!m_on_entry.set_bb_range (name, dom_bb, r))
1674 : 0 : return;
1675 : : }
1676 : : // With the dominator set, we should be able to cheaply query
1677 : : // each incoming edge now and accumulate the results.
1678 : 3493467 : r.set_undefined ();
1679 : 3493467 : edge e;
1680 : 3493467 : edge_iterator ei;
1681 : 3493467 : value_range er (TREE_TYPE (name));
1682 : 11452538 : FOR_EACH_EDGE (e, ei, bb->preds)
1683 : : {
1684 : : // If the predecessor is dominated by this block, then there is a back
1685 : : // edge, and won't provide anything useful. We'll actually end up with
1686 : : // VARYING as we will not resolve this node.
1687 : 7959071 : if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1688 : 21459 : continue;
1689 : 7937612 : edge_range (er, e, name, RFD_READ_ONLY);
1690 : 7937612 : r.union_ (er);
1691 : : }
1692 : : // Set the cache in PREV_BB so it is not calculated again.
1693 : 3493467 : m_on_entry.set_bb_range (name, bb, r);
1694 : 3493467 : }
1695 : :
1696 : : // Get the range of NAME from dominators of BB and return it in R. Search the
1697 : : // dominator tree based on MODE.
1698 : :
1699 : : bool
1700 : 75961258 : ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
1701 : : enum rfd_mode mode)
1702 : : {
1703 : 75961258 : if (mode == RFD_NONE || !dom_info_available_p (CDI_DOMINATORS))
1704 : 22641400 : return false;
1705 : :
1706 : : // Search back to the definition block or entry block.
1707 : 53319858 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1708 : 53319858 : if (def_bb == NULL)
1709 : 7112114 : def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1710 : :
1711 : 53319858 : basic_block bb;
1712 : 53319858 : basic_block prev_bb = start_bb;
1713 : :
1714 : : // Track any inferred ranges seen.
1715 : 53319858 : value_range infer (TREE_TYPE (name));
1716 : 53319858 : infer.set_varying (TREE_TYPE (name));
1717 : :
1718 : : // Range on entry to the DEF block should not be queried.
1719 : 53319858 : gcc_checking_assert (start_bb != def_bb);
1720 : 53319858 : unsigned start_limit = m_workback.length ();
1721 : :
1722 : : // Default value is global range.
1723 : 53319858 : get_global_range (r, name);
1724 : :
1725 : : // The dominator of EXIT_BLOCK doesn't seem to be set, so at least handle
1726 : : // the common single exit cases.
1727 : 53432609 : if (start_bb == EXIT_BLOCK_PTR_FOR_FN (cfun) && single_pred_p (start_bb))
1728 : 112639 : bb = single_pred_edge (start_bb)->src;
1729 : : else
1730 : 53207219 : bb = get_immediate_dominator (CDI_DOMINATORS, start_bb);
1731 : :
1732 : : // Search until a value is found, pushing blocks which may need calculating.
1733 : 339579290 : for ( ; bb; prev_bb = bb, bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1734 : : {
1735 : : // Accumulate any block exit inferred ranges.
1736 : 338957997 : infer_oracle ().maybe_adjust_range (infer, name, bb);
1737 : :
1738 : : // This block has an outgoing range.
1739 : 338957997 : if (gori ().has_edge_range_p (name, bb))
1740 : 37375718 : m_workback.safe_push (prev_bb);
1741 : : else
1742 : : {
1743 : : // Normally join blocks don't carry any new range information on
1744 : : // incoming edges. If the first incoming edge to this block does
1745 : : // generate a range, calculate the ranges if all incoming edges
1746 : : // are also dominated by the dominator. (Avoids backedges which
1747 : : // will break the rule of moving only upward in the dominator tree).
1748 : : // If the first pred does not generate a range, then we will be
1749 : : // using the dominator range anyway, so that's all the check needed.
1750 : 301582279 : if (EDGE_COUNT (prev_bb->preds) > 1
1751 : 301582279 : && gori ().has_edge_range_p (name, EDGE_PRED (prev_bb, 0)->src))
1752 : : {
1753 : 498692 : edge e;
1754 : 498692 : edge_iterator ei;
1755 : 498692 : bool all_dom = true;
1756 : 1642745 : FOR_EACH_EDGE (e, ei, prev_bb->preds)
1757 : 1144053 : if (e->src != bb
1758 : 1144053 : && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
1759 : : {
1760 : : all_dom = false;
1761 : : break;
1762 : : }
1763 : 498692 : if (all_dom)
1764 : 498692 : m_workback.safe_push (prev_bb);
1765 : : }
1766 : : }
1767 : :
1768 : 338957997 : if (def_bb == bb)
1769 : : break;
1770 : :
1771 : 305435901 : if (m_on_entry.get_bb_range (r, name, bb))
1772 : : break;
1773 : : }
1774 : :
1775 : 53319858 : if (DEBUG_RANGE_CACHE)
1776 : : {
1777 : 0 : fprintf (dump_file, "CACHE: BB %d DOM query for ", start_bb->index);
1778 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
1779 : 0 : fprintf (dump_file, ", found ");
1780 : 0 : r.dump (dump_file);
1781 : 0 : if (bb)
1782 : 0 : fprintf (dump_file, " at BB%d\n", bb->index);
1783 : : else
1784 : 0 : fprintf (dump_file, " at function top\n");
1785 : : }
1786 : :
1787 : : // Now process any blocks wit incoming edges that nay have adjustments.
1788 : 91194268 : while (m_workback.length () > start_limit)
1789 : : {
1790 : 37874410 : value_range er (TREE_TYPE (name));
1791 : 37874410 : prev_bb = m_workback.pop ();
1792 : 37874410 : if (!single_pred_p (prev_bb))
1793 : : {
1794 : : // Non single pred means we need to cache a value in the dominator
1795 : : // so we can cheaply calculate incoming edges to this block, and
1796 : : // then store the resulting value. If processing mode is not
1797 : : // RFD_FILL, then the cache cant be stored to, so don't try.
1798 : : // Otherwise this becomes a quadratic timed calculation.
1799 : 6448003 : if (mode == RFD_FILL)
1800 : 3493467 : resolve_dom (r, name, prev_bb);
1801 : 6448003 : continue;
1802 : : }
1803 : :
1804 : 31426407 : edge e = single_pred_edge (prev_bb);
1805 : 31426407 : bb = e->src;
1806 : 31426407 : if (gori ().edge_range_p (er, e, name, *this))
1807 : : {
1808 : 28510103 : r.intersect (er);
1809 : : // If this is a normal edge, apply any inferred ranges.
1810 : 28510103 : if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
1811 : 28510103 : infer_oracle ().maybe_adjust_range (r, name, bb);
1812 : :
1813 : 28510103 : if (DEBUG_RANGE_CACHE)
1814 : : {
1815 : 0 : fprintf (dump_file, "CACHE: Adjusted edge range for %d->%d : ",
1816 : : bb->index, prev_bb->index);
1817 : 0 : r.dump (dump_file);
1818 : 0 : fprintf (dump_file, "\n");
1819 : : }
1820 : : }
1821 : 37874410 : }
1822 : :
1823 : : // Apply non-null if appropriate.
1824 : 53319858 : if (!has_abnormal_call_or_eh_pred_edge_p (start_bb))
1825 : 53239346 : r.intersect (infer);
1826 : :
1827 : 53319858 : if (DEBUG_RANGE_CACHE)
1828 : : {
1829 : 0 : fprintf (dump_file, "CACHE: Range for DOM returns : ");
1830 : 0 : r.dump (dump_file);
1831 : 0 : fprintf (dump_file, "\n");
1832 : : }
1833 : 53319858 : return true;
1834 : 53319858 : }
1835 : :
1836 : : // This routine will register an inferred value in block BB, and possibly
1837 : : // update the on-entry cache if appropriate.
1838 : :
1839 : : void
1840 : 14932793 : ranger_cache::register_inferred_value (const vrange &ir, tree name,
1841 : : basic_block bb)
1842 : : {
1843 : 14932793 : value_range r (TREE_TYPE (name));
1844 : 14932793 : if (!m_on_entry.get_bb_range (r, name, bb))
1845 : 9385127 : exit_range (r, name, bb, RFD_READ_ONLY);
1846 : 14932793 : if (r.intersect (ir))
1847 : : {
1848 : 4509719 : m_on_entry.set_bb_range (name, bb, r);
1849 : : // If this range was invariant before, remove invariant.
1850 : 4509719 : if (!gori ().has_edge_range_p (name))
1851 : 3832742 : gori_ssa ()->set_range_invariant (name, false);
1852 : : }
1853 : 14932793 : }
1854 : :
1855 : : // This routine is used during a block walk to adjust any inferred ranges
1856 : : // of operands on stmt S.
1857 : :
1858 : : void
1859 : 221941295 : ranger_cache::apply_inferred_ranges (gimple *s)
1860 : : {
1861 : 221941295 : bool update = true;
1862 : :
1863 : 221941295 : basic_block bb = gimple_bb (s);
1864 : 221941295 : gimple_infer_range infer(s);
1865 : 221941295 : if (infer.num () == 0)
1866 : : return;
1867 : :
1868 : : // Do not update the on-entry cache for block ending stmts.
1869 : 14684893 : if (stmt_ends_bb_p (s))
1870 : : {
1871 : 1132089 : edge_iterator ei;
1872 : 1132089 : edge e;
1873 : 2045299 : FOR_EACH_EDGE (e, ei, gimple_bb (s)->succs)
1874 : 2039974 : if (!(e->flags & (EDGE_ABNORMAL|EDGE_EH)))
1875 : : break;
1876 : 1132089 : if (e == NULL)
1877 : 5325 : update = false;
1878 : : }
1879 : :
1880 : 14684893 : infer_oracle ().add_ranges (s, infer);
1881 : 14684893 : if (update)
1882 : 29593096 : for (unsigned x = 0; x < infer.num (); x++)
1883 : 14913528 : register_inferred_value (infer.range (x), infer.name (x), bb);
1884 : : }
|
