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