]>
Commit | Line | Data |
---|---|---|
90e88fd3 | 1 | /* Code for GIMPLE range related routines. |
99dee823 | 2 | Copyright (C) 2019-2021 Free Software Foundation, Inc. |
90e88fd3 AM |
3 | Contributed by Andrew MacLeod <amacleod@redhat.com> |
4 | and Aldy Hernandez <aldyh@redhat.com>. | |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 3, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GCC is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GCC; see the file COPYING3. If not see | |
20 | <http://www.gnu.org/licenses/>. */ | |
21 | ||
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "backend.h" | |
26 | #include "insn-codes.h" | |
27 | #include "rtl.h" | |
28 | #include "tree.h" | |
29 | #include "gimple.h" | |
30 | #include "ssa.h" | |
31 | #include "gimple-pretty-print.h" | |
32 | #include "gimple-iterator.h" | |
33 | #include "optabs-tree.h" | |
34 | #include "gimple-fold.h" | |
35 | #include "tree-cfg.h" | |
36 | #include "fold-const.h" | |
37 | #include "tree-cfg.h" | |
38 | #include "wide-int.h" | |
39 | #include "fold-const.h" | |
40 | #include "case-cfn-macros.h" | |
41 | #include "omp-general.h" | |
42 | #include "cfgloop.h" | |
43 | #include "tree-ssa-loop.h" | |
44 | #include "tree-scalar-evolution.h" | |
45 | #include "dbgcnt.h" | |
46 | #include "alloc-pool.h" | |
47 | #include "vr-values.h" | |
48 | #include "gimple-range.h" | |
49 | ||
50 | ||
51 | // Adjust the range for a pointer difference where the operands came | |
52 | // from a memchr. | |
53 | // | |
54 | // This notices the following sequence: | |
55 | // | |
56 | // def = __builtin_memchr (arg, 0, sz) | |
57 | // n = def - arg | |
58 | // | |
59 | // The range for N can be narrowed to [0, PTRDIFF_MAX - 1]. | |
60 | ||
61 | static void | |
62 | adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt) | |
63 | { | |
64 | tree op0 = gimple_assign_rhs1 (diff_stmt); | |
65 | tree op1 = gimple_assign_rhs2 (diff_stmt); | |
66 | tree op0_ptype = TREE_TYPE (TREE_TYPE (op0)); | |
67 | tree op1_ptype = TREE_TYPE (TREE_TYPE (op1)); | |
68 | gimple *call; | |
69 | ||
70 | if (TREE_CODE (op0) == SSA_NAME | |
71 | && TREE_CODE (op1) == SSA_NAME | |
72 | && (call = SSA_NAME_DEF_STMT (op0)) | |
73 | && is_gimple_call (call) | |
74 | && gimple_call_builtin_p (call, BUILT_IN_MEMCHR) | |
75 | && TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node) | |
76 | && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node) | |
77 | && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node) | |
78 | && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node) | |
79 | && gimple_call_builtin_p (call, BUILT_IN_MEMCHR) | |
80 | && vrp_operand_equal_p (op1, gimple_call_arg (call, 0)) | |
81 | && integer_zerop (gimple_call_arg (call, 1))) | |
82 | { | |
83 | tree max = vrp_val_max (ptrdiff_type_node); | |
84 | wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); | |
85 | tree expr_type = gimple_expr_type (diff_stmt); | |
86 | tree range_min = build_zero_cst (expr_type); | |
87 | tree range_max = wide_int_to_tree (expr_type, wmax - 1); | |
88 | int_range<2> r (range_min, range_max); | |
89 | res.intersect (r); | |
90 | } | |
91 | } | |
92 | ||
93 | // This function looks for situations when walking the use/def chains | |
94 | // may provide additonal contextual range information not exposed on | |
95 | // this statement. Like knowing the IMAGPART return value from a | |
96 | // builtin function is a boolean result. | |
97 | ||
98 | // We should rework how we're called, as we have an op_unknown entry | |
99 | // for IMAGPART_EXPR and POINTER_DIFF_EXPR in range-ops just so this | |
100 | // function gets called. | |
101 | ||
102 | static void | |
103 | gimple_range_adjustment (irange &res, const gimple *stmt) | |
104 | { | |
105 | switch (gimple_expr_code (stmt)) | |
106 | { | |
107 | case POINTER_DIFF_EXPR: | |
108 | adjust_pointer_diff_expr (res, stmt); | |
109 | return; | |
110 | ||
111 | case IMAGPART_EXPR: | |
112 | { | |
113 | tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); | |
114 | if (TREE_CODE (name) == SSA_NAME) | |
115 | { | |
116 | gimple *def_stmt = SSA_NAME_DEF_STMT (name); | |
117 | if (def_stmt && is_gimple_call (def_stmt) | |
118 | && gimple_call_internal_p (def_stmt)) | |
119 | { | |
120 | switch (gimple_call_internal_fn (def_stmt)) | |
121 | { | |
122 | case IFN_ADD_OVERFLOW: | |
123 | case IFN_SUB_OVERFLOW: | |
124 | case IFN_MUL_OVERFLOW: | |
125 | case IFN_ATOMIC_COMPARE_EXCHANGE: | |
126 | { | |
127 | int_range<2> r; | |
128 | r.set_varying (boolean_type_node); | |
129 | tree type = TREE_TYPE (gimple_assign_lhs (stmt)); | |
130 | range_cast (r, type); | |
131 | res.intersect (r); | |
132 | } | |
133 | default: | |
134 | break; | |
135 | } | |
136 | } | |
137 | } | |
138 | break; | |
139 | } | |
140 | ||
141 | default: | |
142 | break; | |
143 | } | |
144 | } | |
145 | ||
146 | // Return a range in R for the tree EXPR. Return true if a range is | |
c25d317c | 147 | // representable, and UNDEFINED/false if not. |
90e88fd3 AM |
148 | |
149 | bool | |
150 | get_tree_range (irange &r, tree expr) | |
151 | { | |
152 | tree type; | |
153 | if (TYPE_P (expr)) | |
154 | type = expr; | |
155 | else | |
156 | type = TREE_TYPE (expr); | |
157 | ||
158 | // Return false if the type isn't suported. | |
159 | if (!irange::supports_type_p (type)) | |
c25d317c AM |
160 | { |
161 | r.set_undefined (); | |
162 | return false; | |
163 | } | |
90e88fd3 AM |
164 | |
165 | switch (TREE_CODE (expr)) | |
166 | { | |
167 | case INTEGER_CST: | |
4ef0f1e9 AH |
168 | if (TREE_OVERFLOW_P (expr)) |
169 | expr = drop_tree_overflow (expr); | |
90e88fd3 AM |
170 | r.set (expr, expr); |
171 | return true; | |
172 | ||
173 | case SSA_NAME: | |
174 | r = gimple_range_global (expr); | |
175 | return true; | |
176 | ||
177 | case ADDR_EXPR: | |
178 | { | |
179 | // Handle &var which can show up in phi arguments. | |
180 | bool ov; | |
181 | if (tree_single_nonzero_warnv_p (expr, &ov)) | |
182 | { | |
183 | r = range_nonzero (type); | |
184 | return true; | |
185 | } | |
186 | break; | |
187 | } | |
188 | ||
189 | default: | |
190 | break; | |
191 | } | |
192 | r.set_varying (type); | |
193 | return true; | |
194 | } | |
195 | ||
196 | // Fold this unary statement using R1 as operand1's range, returning | |
197 | // the result in RES. Return false if the operation fails. | |
198 | ||
199 | bool | |
200 | gimple_range_fold (irange &res, const gimple *stmt, const irange &r1) | |
201 | { | |
202 | gcc_checking_assert (gimple_range_handler (stmt)); | |
203 | ||
204 | tree type = gimple_expr_type (stmt); | |
205 | // Unary SSA operations require the LHS type as the second range. | |
206 | int_range<2> r2 (type); | |
207 | ||
208 | return gimple_range_fold (res, stmt, r1, r2); | |
209 | } | |
210 | ||
211 | // Fold this binary statement using R1 and R2 as the operands ranges, | |
212 | // returning the result in RES. Return false if the operation fails. | |
213 | ||
214 | bool | |
215 | gimple_range_fold (irange &res, const gimple *stmt, | |
216 | const irange &r1, const irange &r2) | |
217 | { | |
218 | gcc_checking_assert (gimple_range_handler (stmt)); | |
219 | ||
220 | gimple_range_handler (stmt)->fold_range (res, gimple_expr_type (stmt), | |
221 | r1, r2); | |
222 | ||
223 | // If there are any gimple lookups, do those now. | |
224 | gimple_range_adjustment (res, stmt); | |
225 | return true; | |
226 | } | |
227 | ||
228 | // Return the base of the RHS of an assignment. | |
229 | ||
230 | tree | |
231 | gimple_range_base_of_assignment (const gimple *stmt) | |
232 | { | |
233 | gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN); | |
234 | tree op1 = gimple_assign_rhs1 (stmt); | |
235 | if (gimple_assign_rhs_code (stmt) == ADDR_EXPR) | |
236 | return get_base_address (TREE_OPERAND (op1, 0)); | |
237 | return op1; | |
238 | } | |
239 | ||
240 | // Return the first operand of this statement if it is a valid operand | |
241 | // supported by ranges, otherwise return NULL_TREE. Special case is | |
242 | // &(SSA_NAME expr), return the SSA_NAME instead of the ADDR expr. | |
243 | ||
244 | tree | |
245 | gimple_range_operand1 (const gimple *stmt) | |
246 | { | |
247 | gcc_checking_assert (gimple_range_handler (stmt)); | |
248 | ||
249 | switch (gimple_code (stmt)) | |
250 | { | |
251 | case GIMPLE_COND: | |
252 | return gimple_cond_lhs (stmt); | |
253 | case GIMPLE_ASSIGN: | |
254 | { | |
255 | tree base = gimple_range_base_of_assignment (stmt); | |
256 | if (base && TREE_CODE (base) == MEM_REF) | |
257 | { | |
258 | // If the base address is an SSA_NAME, we return it | |
259 | // here. This allows processing of the range of that | |
260 | // name, while the rest of the expression is simply | |
261 | // ignored. The code in range_ops will see the | |
262 | // ADDR_EXPR and do the right thing. | |
263 | tree ssa = TREE_OPERAND (base, 0); | |
264 | if (TREE_CODE (ssa) == SSA_NAME) | |
265 | return ssa; | |
266 | } | |
267 | return base; | |
268 | } | |
269 | default: | |
270 | break; | |
271 | } | |
272 | return NULL; | |
273 | } | |
274 | ||
275 | // Return the second operand of statement STMT, otherwise return NULL_TREE. | |
276 | ||
277 | tree | |
278 | gimple_range_operand2 (const gimple *stmt) | |
279 | { | |
280 | gcc_checking_assert (gimple_range_handler (stmt)); | |
281 | ||
282 | switch (gimple_code (stmt)) | |
283 | { | |
284 | case GIMPLE_COND: | |
285 | return gimple_cond_rhs (stmt); | |
286 | case GIMPLE_ASSIGN: | |
287 | if (gimple_num_ops (stmt) >= 3) | |
288 | return gimple_assign_rhs2 (stmt); | |
289 | default: | |
290 | break; | |
291 | } | |
292 | return NULL_TREE; | |
293 | } | |
294 | ||
295 | // Calculate what we can determine of the range of this unary | |
296 | // statement's operand if the lhs of the expression has the range | |
297 | // LHS_RANGE. Return false if nothing can be determined. | |
298 | ||
299 | bool | |
300 | gimple_range_calc_op1 (irange &r, const gimple *stmt, const irange &lhs_range) | |
301 | { | |
302 | gcc_checking_assert (gimple_num_ops (stmt) < 3); | |
303 | ||
304 | // An empty range is viral. | |
305 | tree type = TREE_TYPE (gimple_range_operand1 (stmt)); | |
306 | if (lhs_range.undefined_p ()) | |
307 | { | |
308 | r.set_undefined (); | |
309 | return true; | |
310 | } | |
311 | // Unary operations require the type of the first operand in the | |
312 | // second range position. | |
313 | int_range<2> type_range (type); | |
314 | return gimple_range_handler (stmt)->op1_range (r, type, lhs_range, | |
315 | type_range); | |
316 | } | |
317 | ||
318 | // Calculate what we can determine of the range of this statement's | |
319 | // first operand if the lhs of the expression has the range LHS_RANGE | |
320 | // and the second operand has the range OP2_RANGE. Return false if | |
321 | // nothing can be determined. | |
322 | ||
323 | bool | |
324 | gimple_range_calc_op1 (irange &r, const gimple *stmt, | |
325 | const irange &lhs_range, const irange &op2_range) | |
326 | { | |
327 | // Unary operation are allowed to pass a range in for second operand | |
328 | // as there are often additional restrictions beyond the type which | |
329 | // can be imposed. See operator_cast::op1_range(). | |
330 | tree type = TREE_TYPE (gimple_range_operand1 (stmt)); | |
331 | // An empty range is viral. | |
332 | if (op2_range.undefined_p () || lhs_range.undefined_p ()) | |
333 | { | |
334 | r.set_undefined (); | |
335 | return true; | |
336 | } | |
337 | return gimple_range_handler (stmt)->op1_range (r, type, lhs_range, | |
338 | op2_range); | |
339 | } | |
340 | ||
341 | // Calculate what we can determine of the range of this statement's | |
342 | // second operand if the lhs of the expression has the range LHS_RANGE | |
343 | // and the first operand has the range OP1_RANGE. Return false if | |
344 | // nothing can be determined. | |
345 | ||
346 | bool | |
347 | gimple_range_calc_op2 (irange &r, const gimple *stmt, | |
348 | const irange &lhs_range, const irange &op1_range) | |
349 | { | |
350 | tree type = TREE_TYPE (gimple_range_operand2 (stmt)); | |
351 | // An empty range is viral. | |
352 | if (op1_range.undefined_p () || lhs_range.undefined_p ()) | |
353 | { | |
354 | r.set_undefined (); | |
355 | return true; | |
356 | } | |
357 | return gimple_range_handler (stmt)->op2_range (r, type, lhs_range, | |
358 | op1_range); | |
359 | } | |
360 | ||
361 | // Calculate a range for statement S and return it in R. If NAME is provided it | |
362 | // represents the SSA_NAME on the LHS of the statement. It is only required | |
363 | // if there is more than one lhs/output. If a range cannot | |
364 | // be calculated, return false. | |
365 | ||
366 | bool | |
367 | gimple_ranger::calc_stmt (irange &r, gimple *s, tree name) | |
368 | { | |
369 | bool res = false; | |
370 | // If name is specified, make sure it is an LHS of S. | |
371 | gcc_checking_assert (name ? SSA_NAME_DEF_STMT (name) == s : true); | |
372 | ||
373 | if (gimple_range_handler (s)) | |
374 | res = range_of_range_op (r, s); | |
375 | else if (is_a<gphi *>(s)) | |
376 | res = range_of_phi (r, as_a<gphi *> (s)); | |
377 | else if (is_a<gcall *>(s)) | |
378 | res = range_of_call (r, as_a<gcall *> (s)); | |
379 | else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR) | |
380 | res = range_of_cond_expr (r, as_a<gassign *> (s)); | |
c25d317c AM |
381 | |
382 | if (!res) | |
90e88fd3 AM |
383 | { |
384 | // If no name is specified, try the expression kind. | |
385 | if (!name) | |
386 | { | |
387 | tree t = gimple_expr_type (s); | |
388 | if (!irange::supports_type_p (t)) | |
389 | return false; | |
390 | r.set_varying (t); | |
391 | return true; | |
392 | } | |
c25d317c AM |
393 | if (!gimple_range_ssa_p (name)) |
394 | return false; | |
90e88fd3 AM |
395 | // We don't understand the stmt, so return the global range. |
396 | r = gimple_range_global (name); | |
397 | return true; | |
398 | } | |
c25d317c AM |
399 | |
400 | if (r.undefined_p ()) | |
401 | return true; | |
402 | ||
403 | // We sometimes get compatible types copied from operands, make sure | |
404 | // the correct type is being returned. | |
405 | if (name && TREE_TYPE (name) != r.type ()) | |
90e88fd3 | 406 | { |
c25d317c AM |
407 | gcc_checking_assert (range_compatible_p (r.type (), TREE_TYPE (name))); |
408 | range_cast (r, TREE_TYPE (name)); | |
90e88fd3 | 409 | } |
c25d317c | 410 | return true; |
90e88fd3 AM |
411 | } |
412 | ||
413 | // Calculate a range for range_op statement S and return it in R. If any | |
414 | // If a range cannot be calculated, return false. | |
415 | ||
416 | bool | |
417 | gimple_ranger::range_of_range_op (irange &r, gimple *s) | |
418 | { | |
419 | int_range_max range1, range2; | |
e86fd6a1 | 420 | tree lhs = gimple_get_lhs (s); |
90e88fd3 AM |
421 | tree type = gimple_expr_type (s); |
422 | gcc_checking_assert (irange::supports_type_p (type)); | |
423 | ||
424 | tree op1 = gimple_range_operand1 (s); | |
425 | tree op2 = gimple_range_operand2 (s); | |
426 | ||
e86fd6a1 AM |
427 | if (lhs) |
428 | { | |
429 | // Register potential dependencies for stale value tracking. | |
430 | m_cache.register_dependency (lhs, op1); | |
431 | m_cache.register_dependency (lhs, op2); | |
432 | } | |
433 | ||
47923622 AM |
434 | if (gimple_code (s) == GIMPLE_ASSIGN |
435 | && gimple_assign_rhs_code (s) == ADDR_EXPR) | |
436 | return range_of_address (r, s); | |
90e88fd3 AM |
437 | |
438 | if (range_of_expr (range1, op1, s)) | |
439 | { | |
440 | if (!op2) | |
441 | return gimple_range_fold (r, s, range1); | |
442 | ||
443 | if (range_of_expr (range2, op2, s)) | |
444 | return gimple_range_fold (r, s, range1, range2); | |
445 | } | |
446 | r.set_varying (type); | |
447 | return true; | |
448 | } | |
449 | ||
47923622 | 450 | // Calculate the range of an assignment containing an ADDR_EXPR. |
90e88fd3 | 451 | // Return the range in R. |
47923622 | 452 | // If a range cannot be calculated, set it to VARYING and return true. |
90e88fd3 AM |
453 | |
454 | bool | |
47923622 | 455 | gimple_ranger::range_of_address (irange &r, gimple *stmt) |
90e88fd3 | 456 | { |
47923622 AM |
457 | gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN); |
458 | gcc_checking_assert (gimple_assign_rhs_code (stmt) == ADDR_EXPR); | |
459 | ||
460 | bool strict_overflow_p; | |
461 | tree expr = gimple_assign_rhs1 (stmt); | |
462 | poly_int64 bitsize, bitpos; | |
463 | tree offset; | |
464 | machine_mode mode; | |
465 | int unsignedp, reversep, volatilep; | |
466 | tree base = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, | |
467 | &bitpos, &offset, &mode, &unsignedp, | |
468 | &reversep, &volatilep); | |
469 | ||
470 | ||
471 | if (base != NULL_TREE | |
472 | && TREE_CODE (base) == MEM_REF | |
473 | && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) | |
90e88fd3 | 474 | { |
47923622 AM |
475 | tree ssa = TREE_OPERAND (base, 0); |
476 | gcc_checking_assert (irange::supports_type_p (TREE_TYPE (ssa))); | |
477 | range_of_expr (r, ssa, stmt); | |
478 | range_cast (r, TREE_TYPE (gimple_assign_rhs1 (stmt))); | |
479 | ||
480 | poly_offset_int off = 0; | |
481 | bool off_cst = false; | |
482 | if (offset == NULL_TREE || TREE_CODE (offset) == INTEGER_CST) | |
90e88fd3 | 483 | { |
47923622 AM |
484 | off = mem_ref_offset (base); |
485 | if (offset) | |
486 | off += poly_offset_int::from (wi::to_poly_wide (offset), | |
487 | SIGNED); | |
488 | off <<= LOG2_BITS_PER_UNIT; | |
489 | off += bitpos; | |
490 | off_cst = true; | |
966fdb2e | 491 | } |
47923622 AM |
492 | /* If &X->a is equal to X, the range of X is the result. */ |
493 | if (off_cst && known_eq (off, 0)) | |
494 | return true; | |
495 | else if (flag_delete_null_pointer_checks | |
496 | && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))) | |
497 | { | |
498 | /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't | |
499 | allow going from non-NULL pointer to NULL. */ | |
500 | if(!range_includes_zero_p (&r)) | |
501 | return true; | |
502 | } | |
503 | /* If MEM_REF has a "positive" offset, consider it non-NULL | |
504 | always, for -fdelete-null-pointer-checks also "negative" | |
505 | ones. Punt for unknown offsets (e.g. variable ones). */ | |
506 | if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)) | |
507 | && off_cst | |
508 | && known_ne (off, 0) | |
509 | && (flag_delete_null_pointer_checks || known_gt (off, 0))) | |
966fdb2e | 510 | { |
966fdb2e | 511 | r = range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt))); |
90e88fd3 AM |
512 | return true; |
513 | } | |
47923622 AM |
514 | r = int_range<2> (TREE_TYPE (gimple_assign_rhs1 (stmt))); |
515 | return true; | |
90e88fd3 | 516 | } |
47923622 AM |
517 | |
518 | // Handle "= &a". | |
519 | if (tree_single_nonzero_warnv_p (expr, &strict_overflow_p)) | |
520 | { | |
521 | r = range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt))); | |
522 | return true; | |
523 | } | |
524 | ||
525 | // Otherwise return varying. | |
526 | r = int_range<2> (TREE_TYPE (gimple_assign_rhs1 (stmt))); | |
527 | return true; | |
90e88fd3 AM |
528 | } |
529 | ||
530 | // Calculate a range for phi statement S and return it in R. | |
531 | // If a range cannot be calculated, return false. | |
532 | ||
533 | bool | |
534 | gimple_ranger::range_of_phi (irange &r, gphi *phi) | |
535 | { | |
536 | tree phi_def = gimple_phi_result (phi); | |
537 | tree type = TREE_TYPE (phi_def); | |
538 | int_range_max arg_range; | |
539 | unsigned x; | |
540 | ||
541 | if (!irange::supports_type_p (type)) | |
542 | return false; | |
543 | ||
544 | // Start with an empty range, unioning in each argument's range. | |
545 | r.set_undefined (); | |
546 | for (x = 0; x < gimple_phi_num_args (phi); x++) | |
547 | { | |
548 | tree arg = gimple_phi_arg_def (phi, x); | |
549 | edge e = gimple_phi_arg_edge (phi, x); | |
550 | ||
e86fd6a1 AM |
551 | // Register potential dependencies for stale value tracking. |
552 | m_cache.register_dependency (phi_def, arg); | |
553 | ||
90e88fd3 AM |
554 | range_on_edge (arg_range, e, arg); |
555 | r.union_ (arg_range); | |
556 | // Once the value reaches varying, stop looking. | |
557 | if (r.varying_p ()) | |
558 | break; | |
559 | } | |
560 | ||
561 | // If SCEV is available, query if this PHI has any knonwn values. | |
562 | if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def))) | |
563 | { | |
564 | value_range loop_range; | |
565 | class loop *l = loop_containing_stmt (phi); | |
a121715b | 566 | if (l && loop_outer (l)) |
90e88fd3 AM |
567 | { |
568 | range_of_ssa_name_with_loop_info (loop_range, phi_def, l, phi); | |
569 | if (!loop_range.varying_p ()) | |
570 | { | |
571 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
572 | { | |
573 | fprintf (dump_file, " Loops range found for "); | |
574 | print_generic_expr (dump_file, phi_def, TDF_SLIM); | |
575 | fprintf (dump_file, ": "); | |
576 | loop_range.dump (dump_file); | |
577 | fprintf (dump_file, " and calculated range :"); | |
578 | r.dump (dump_file); | |
579 | fprintf (dump_file, "\n"); | |
580 | } | |
581 | r.intersect (loop_range); | |
582 | } | |
583 | } | |
584 | } | |
585 | ||
586 | return true; | |
587 | } | |
588 | ||
589 | // Calculate a range for call statement S and return it in R. | |
590 | // If a range cannot be calculated, return false. | |
591 | ||
592 | bool | |
593 | gimple_ranger::range_of_call (irange &r, gcall *call) | |
594 | { | |
595 | tree type = gimple_call_return_type (call); | |
596 | tree lhs = gimple_call_lhs (call); | |
597 | bool strict_overflow_p; | |
598 | ||
599 | if (!irange::supports_type_p (type)) | |
600 | return false; | |
601 | ||
602 | if (range_of_builtin_call (r, call)) | |
603 | ; | |
604 | else if (gimple_stmt_nonnegative_warnv_p (call, &strict_overflow_p)) | |
605 | r.set (build_int_cst (type, 0), TYPE_MAX_VALUE (type)); | |
606 | else if (gimple_call_nonnull_result_p (call) | |
607 | || gimple_call_nonnull_arg (call)) | |
608 | r = range_nonzero (type); | |
609 | else | |
610 | r.set_varying (type); | |
611 | ||
612 | // If there is an LHS, intersect that with what is known. | |
613 | if (lhs) | |
614 | { | |
615 | value_range def; | |
616 | def = gimple_range_global (lhs); | |
617 | r.intersect (def); | |
618 | } | |
619 | return true; | |
620 | } | |
621 | ||
16e4f1ad AH |
622 | // Return the range of a __builtin_ubsan* in CALL and set it in R. |
623 | // CODE is the type of ubsan call (PLUS_EXPR, MINUS_EXPR or | |
624 | // MULT_EXPR). | |
90e88fd3 | 625 | |
16e4f1ad AH |
626 | static void |
627 | range_of_builtin_ubsan_call (range_query &query, irange &r, gcall *call, | |
628 | tree_code code) | |
90e88fd3 AM |
629 | { |
630 | gcc_checking_assert (code == PLUS_EXPR || code == MINUS_EXPR | |
631 | || code == MULT_EXPR); | |
632 | tree type = gimple_call_return_type (call); | |
633 | range_operator *op = range_op_handler (code, type); | |
634 | gcc_checking_assert (op); | |
635 | int_range_max ir0, ir1; | |
636 | tree arg0 = gimple_call_arg (call, 0); | |
637 | tree arg1 = gimple_call_arg (call, 1); | |
c25d317c AM |
638 | query.range_of_expr (ir0, arg0, call); |
639 | query.range_of_expr (ir1, arg1, call); | |
90e88fd3 AM |
640 | |
641 | bool saved_flag_wrapv = flag_wrapv; | |
642 | // Pretend the arithmetic is wrapping. If there is any overflow, | |
643 | // we'll complain, but will actually do wrapping operation. | |
644 | flag_wrapv = 1; | |
645 | op->fold_range (r, type, ir0, ir1); | |
646 | flag_wrapv = saved_flag_wrapv; | |
647 | ||
648 | // If for both arguments vrp_valueize returned non-NULL, this should | |
649 | // have been already folded and if not, it wasn't folded because of | |
650 | // overflow. Avoid removing the UBSAN_CHECK_* calls in that case. | |
651 | if (r.singleton_p ()) | |
652 | r.set_varying (type); | |
653 | } | |
654 | ||
16e4f1ad AH |
655 | // For a builtin in CALL, return a range in R if known and return |
656 | // TRUE. Otherwise return FALSE. | |
90e88fd3 AM |
657 | |
658 | bool | |
16e4f1ad | 659 | range_of_builtin_call (range_query &query, irange &r, gcall *call) |
90e88fd3 AM |
660 | { |
661 | combined_fn func = gimple_call_combined_fn (call); | |
662 | if (func == CFN_LAST) | |
663 | return false; | |
664 | ||
665 | tree type = gimple_call_return_type (call); | |
666 | tree arg; | |
425bb53b | 667 | int mini, maxi, zerov = 0, prec; |
90e88fd3 AM |
668 | scalar_int_mode mode; |
669 | ||
670 | switch (func) | |
671 | { | |
672 | case CFN_BUILT_IN_CONSTANT_P: | |
673 | if (cfun->after_inlining) | |
674 | { | |
675 | r.set_zero (type); | |
676 | // r.equiv_clear (); | |
677 | return true; | |
678 | } | |
679 | arg = gimple_call_arg (call, 0); | |
16e4f1ad | 680 | if (query.range_of_expr (r, arg, call) && r.singleton_p ()) |
90e88fd3 AM |
681 | { |
682 | r.set (build_one_cst (type), build_one_cst (type)); | |
683 | return true; | |
684 | } | |
685 | break; | |
686 | ||
687 | CASE_CFN_FFS: | |
688 | CASE_CFN_POPCOUNT: | |
689 | // __builtin_ffs* and __builtin_popcount* return [0, prec]. | |
690 | arg = gimple_call_arg (call, 0); | |
691 | prec = TYPE_PRECISION (TREE_TYPE (arg)); | |
692 | mini = 0; | |
693 | maxi = prec; | |
c25d317c | 694 | query.range_of_expr (r, arg, call); |
90e88fd3 AM |
695 | // If arg is non-zero, then ffs or popcount are non-zero. |
696 | if (!range_includes_zero_p (&r)) | |
697 | mini = 1; | |
698 | // If some high bits are known to be zero, decrease the maximum. | |
699 | if (!r.undefined_p ()) | |
700 | { | |
9489806f AH |
701 | if (TYPE_SIGN (r.type ()) == SIGNED) |
702 | range_cast (r, unsigned_type_for (r.type ())); | |
90e88fd3 AM |
703 | wide_int max = r.upper_bound (); |
704 | maxi = wi::floor_log2 (max) + 1; | |
705 | } | |
706 | r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); | |
707 | return true; | |
708 | ||
709 | CASE_CFN_PARITY: | |
710 | r.set (build_zero_cst (type), build_one_cst (type)); | |
711 | return true; | |
712 | ||
713 | CASE_CFN_CLZ: | |
714 | // __builtin_c[lt]z* return [0, prec-1], except when the | |
715 | // argument is 0, but that is undefined behavior. | |
716 | // | |
781634da JJ |
717 | // For __builtin_c[lt]z* consider argument of 0 always undefined |
718 | // behavior, for internal fns depending on C?Z_DEFINED_VALUE_AT_ZERO. | |
90e88fd3 AM |
719 | arg = gimple_call_arg (call, 0); |
720 | prec = TYPE_PRECISION (TREE_TYPE (arg)); | |
721 | mini = 0; | |
781634da | 722 | maxi = prec - 1; |
90e88fd3 | 723 | mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg)); |
781634da JJ |
724 | if (gimple_call_internal_p (call)) |
725 | { | |
726 | if (optab_handler (clz_optab, mode) != CODE_FOR_nothing | |
727 | && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov) == 2) | |
728 | { | |
729 | // Only handle the single common value. | |
730 | if (zerov == prec) | |
731 | maxi = prec; | |
732 | else | |
733 | // Magic value to give up, unless we can prove arg is non-zero. | |
734 | mini = -2; | |
735 | } | |
736 | } | |
90e88fd3 | 737 | |
c25d317c | 738 | query.range_of_expr (r, arg, call); |
90e88fd3 AM |
739 | // From clz of minimum we can compute result maximum. |
740 | if (r.constant_p ()) | |
741 | { | |
781634da JJ |
742 | int newmaxi = prec - 1 - wi::floor_log2 (r.lower_bound ()); |
743 | // Argument is unsigned, so do nothing if it is [0, ...] range. | |
744 | if (newmaxi != prec) | |
745 | { | |
746 | mini = 0; | |
747 | maxi = newmaxi; | |
748 | } | |
90e88fd3 AM |
749 | } |
750 | else if (!range_includes_zero_p (&r)) | |
751 | { | |
752 | maxi = prec - 1; | |
753 | mini = 0; | |
754 | } | |
755 | if (mini == -2) | |
756 | break; | |
757 | // From clz of maximum we can compute result minimum. | |
758 | if (r.constant_p ()) | |
759 | { | |
781634da JJ |
760 | int newmini = prec - 1 - wi::floor_log2 (r.upper_bound ()); |
761 | if (newmini == prec) | |
762 | { | |
763 | // Argument range is [0, 0]. If CLZ_DEFINED_VALUE_AT_ZERO | |
764 | // is 2 with VALUE of prec, return [prec, prec], otherwise | |
765 | // ignore the range. | |
766 | if (maxi == prec) | |
767 | mini = prec; | |
768 | } | |
769 | else | |
770 | mini = newmini; | |
90e88fd3 AM |
771 | } |
772 | if (mini == -2) | |
773 | break; | |
774 | r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); | |
775 | return true; | |
776 | ||
777 | CASE_CFN_CTZ: | |
778 | // __builtin_ctz* return [0, prec-1], except for when the | |
779 | // argument is 0, but that is undefined behavior. | |
780 | // | |
781634da JJ |
781 | // For __builtin_ctz* consider argument of 0 always undefined |
782 | // behavior, for internal fns depending on CTZ_DEFINED_VALUE_AT_ZERO. | |
90e88fd3 AM |
783 | arg = gimple_call_arg (call, 0); |
784 | prec = TYPE_PRECISION (TREE_TYPE (arg)); | |
785 | mini = 0; | |
786 | maxi = prec - 1; | |
787 | mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg)); | |
781634da | 788 | if (gimple_call_internal_p (call)) |
90e88fd3 | 789 | { |
781634da JJ |
790 | if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing |
791 | && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov) == 2) | |
792 | { | |
793 | // Handle only the two common values. | |
794 | if (zerov == -1) | |
795 | mini = -1; | |
796 | else if (zerov == prec) | |
797 | maxi = prec; | |
798 | else | |
799 | // Magic value to give up, unless we can prove arg is non-zero. | |
800 | mini = -2; | |
801 | } | |
90e88fd3 | 802 | } |
c25d317c | 803 | query.range_of_expr (r, arg, call); |
90e88fd3 AM |
804 | if (!r.undefined_p ()) |
805 | { | |
806 | if (r.lower_bound () != 0) | |
807 | { | |
808 | mini = 0; | |
809 | maxi = prec - 1; | |
810 | } | |
811 | // If some high bits are known to be zero, we can decrease | |
812 | // the maximum. | |
813 | wide_int max = r.upper_bound (); | |
814 | if (max == 0) | |
781634da JJ |
815 | { |
816 | // Argument is [0, 0]. If CTZ_DEFINED_VALUE_AT_ZERO | |
817 | // is 2 with value -1 or prec, return [-1, -1] or [prec, prec]. | |
818 | // Otherwise ignore the range. | |
819 | if (mini == -1) | |
820 | maxi = -1; | |
821 | else if (maxi == prec) | |
822 | mini = prec; | |
823 | } | |
824 | // If value at zero is prec and 0 is in the range, we can't lower | |
825 | // the upper bound. We could create two separate ranges though, | |
826 | // [0,floor_log2(max)][prec,prec] though. | |
827 | else if (maxi != prec) | |
828 | maxi = wi::floor_log2 (max); | |
90e88fd3 AM |
829 | } |
830 | if (mini == -2) | |
831 | break; | |
832 | r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); | |
833 | return true; | |
834 | ||
835 | CASE_CFN_CLRSB: | |
836 | arg = gimple_call_arg (call, 0); | |
837 | prec = TYPE_PRECISION (TREE_TYPE (arg)); | |
838 | r.set (build_int_cst (type, 0), build_int_cst (type, prec - 1)); | |
839 | return true; | |
840 | case CFN_UBSAN_CHECK_ADD: | |
16e4f1ad | 841 | range_of_builtin_ubsan_call (query, r, call, PLUS_EXPR); |
90e88fd3 AM |
842 | return true; |
843 | case CFN_UBSAN_CHECK_SUB: | |
16e4f1ad | 844 | range_of_builtin_ubsan_call (query, r, call, MINUS_EXPR); |
90e88fd3 AM |
845 | return true; |
846 | case CFN_UBSAN_CHECK_MUL: | |
16e4f1ad | 847 | range_of_builtin_ubsan_call (query, r, call, MULT_EXPR); |
90e88fd3 AM |
848 | return true; |
849 | ||
850 | case CFN_GOACC_DIM_SIZE: | |
851 | case CFN_GOACC_DIM_POS: | |
852 | // Optimizing these two internal functions helps the loop | |
853 | // optimizer eliminate outer comparisons. Size is [1,N] | |
854 | // and pos is [0,N-1]. | |
855 | { | |
856 | bool is_pos = func == CFN_GOACC_DIM_POS; | |
857 | int axis = oacc_get_ifn_dim_arg (call); | |
858 | int size = oacc_get_fn_dim_size (current_function_decl, axis); | |
859 | if (!size) | |
860 | // If it's dynamic, the backend might know a hardware limitation. | |
861 | size = targetm.goacc.dim_limit (axis); | |
862 | ||
863 | r.set (build_int_cst (type, is_pos ? 0 : 1), | |
864 | size | |
865 | ? build_int_cst (type, size - is_pos) : vrp_val_max (type)); | |
866 | return true; | |
867 | } | |
868 | ||
869 | case CFN_BUILT_IN_STRLEN: | |
870 | if (tree lhs = gimple_call_lhs (call)) | |
871 | if (ptrdiff_type_node | |
872 | && (TYPE_PRECISION (ptrdiff_type_node) | |
873 | == TYPE_PRECISION (TREE_TYPE (lhs)))) | |
874 | { | |
875 | tree type = TREE_TYPE (lhs); | |
876 | tree max = vrp_val_max (ptrdiff_type_node); | |
877 | wide_int wmax | |
878 | = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); | |
879 | tree range_min = build_zero_cst (type); | |
880 | // To account for the terminating NULL, the maximum length | |
881 | // is one less than the maximum array size, which in turn | |
882 | // is one less than PTRDIFF_MAX (or SIZE_MAX where it's | |
883 | // smaller than the former type). | |
884 | // FIXME: Use max_object_size() - 1 here. | |
885 | tree range_max = wide_int_to_tree (type, wmax - 2); | |
886 | r.set (range_min, range_max); | |
887 | return true; | |
888 | } | |
889 | break; | |
890 | default: | |
891 | break; | |
892 | } | |
893 | return false; | |
894 | } | |
895 | ||
896 | ||
16e4f1ad AH |
897 | bool |
898 | gimple_ranger::range_of_builtin_call (irange &r, gcall *call) | |
899 | { | |
900 | return ::range_of_builtin_call (*this, r, call); | |
901 | } | |
90e88fd3 AM |
902 | |
903 | // Calculate a range for COND_EXPR statement S and return it in R. | |
904 | // If a range cannot be calculated, return false. | |
905 | ||
906 | bool | |
907 | gimple_ranger::range_of_cond_expr (irange &r, gassign *s) | |
908 | { | |
909 | int_range_max cond_range, range1, range2; | |
910 | tree cond = gimple_assign_rhs1 (s); | |
911 | tree op1 = gimple_assign_rhs2 (s); | |
912 | tree op2 = gimple_assign_rhs3 (s); | |
913 | ||
914 | gcc_checking_assert (gimple_assign_rhs_code (s) == COND_EXPR); | |
915 | gcc_checking_assert (useless_type_conversion_p (TREE_TYPE (op1), | |
916 | TREE_TYPE (op2))); | |
917 | if (!irange::supports_type_p (TREE_TYPE (op1))) | |
918 | return false; | |
919 | ||
c25d317c AM |
920 | range_of_expr (cond_range, cond, s); |
921 | range_of_expr (range1, op1, s); | |
922 | range_of_expr (range2, op2, s); | |
90e88fd3 AM |
923 | |
924 | // If the condition is known, choose the appropriate expression. | |
925 | if (cond_range.singleton_p ()) | |
926 | { | |
927 | // False, pick second operand. | |
928 | if (cond_range.zero_p ()) | |
929 | r = range2; | |
930 | else | |
931 | r = range1; | |
932 | } | |
933 | else | |
934 | { | |
935 | r = range1; | |
936 | r.union_ (range2); | |
937 | } | |
938 | return true; | |
939 | } | |
940 | ||
941 | bool | |
942 | gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) | |
943 | { | |
944 | if (!gimple_range_ssa_p (expr)) | |
945 | return get_tree_range (r, expr); | |
946 | ||
947 | // If there is no statement, just get the global value. | |
948 | if (!stmt) | |
949 | { | |
220929c0 | 950 | if (!m_cache.get_global_range (r, expr)) |
90e88fd3 AM |
951 | r = gimple_range_global (expr); |
952 | return true; | |
953 | } | |
954 | ||
955 | basic_block bb = gimple_bb (stmt); | |
956 | gimple *def_stmt = SSA_NAME_DEF_STMT (expr); | |
957 | ||
958 | // If name is defined in this block, try to get an range from S. | |
959 | if (def_stmt && gimple_bb (def_stmt) == bb) | |
c25d317c | 960 | range_of_stmt (r, def_stmt, expr); |
90e88fd3 AM |
961 | else |
962 | // Otherwise OP comes from outside this block, use range on entry. | |
963 | range_on_entry (r, bb, expr); | |
964 | ||
965 | // No range yet, see if there is a dereference in the block. | |
966 | // We don't care if it's between the def and a use within a block | |
967 | // because the entire block must be executed anyway. | |
968 | // FIXME:?? For non-call exceptions we could have a statement throw | |
969 | // which causes an early block exit. | |
970 | // in which case we may need to walk from S back to the def/top of block | |
971 | // to make sure the deref happens between S and there before claiming | |
972 | // there is a deref. Punt for now. | |
973 | if (!cfun->can_throw_non_call_exceptions && r.varying_p () && | |
974 | m_cache.m_non_null.non_null_deref_p (expr, bb)) | |
975 | r = range_nonzero (TREE_TYPE (expr)); | |
976 | ||
977 | return true; | |
978 | } | |
979 | ||
980 | // Return the range of NAME on entry to block BB in R. | |
981 | ||
982 | void | |
983 | gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name) | |
984 | { | |
985 | int_range_max entry_range; | |
986 | gcc_checking_assert (gimple_range_ssa_p (name)); | |
987 | ||
988 | // Start with any known range | |
c25d317c | 989 | range_of_stmt (r, SSA_NAME_DEF_STMT (name), name); |
90e88fd3 AM |
990 | |
991 | // Now see if there is any on_entry value which may refine it. | |
992 | if (m_cache.block_range (entry_range, bb, name)) | |
993 | r.intersect (entry_range); | |
994 | } | |
995 | ||
996 | // Calculate the range for NAME at the end of block BB and return it in R. | |
997 | // Return false if no range can be calculated. | |
998 | ||
999 | void | |
1000 | gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name) | |
1001 | { | |
1002 | // on-exit from the exit block? | |
1003 | gcc_checking_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); | |
c25d317c | 1004 | gcc_checking_assert (gimple_range_ssa_p (name)); |
90e88fd3 AM |
1005 | |
1006 | gimple *s = last_stmt (bb); | |
1007 | // If there is no statement in the block and this isn't the entry | |
1008 | // block, go get the range_on_entry for this block. For the entry | |
1009 | // block, a NULL stmt will return the global value for NAME. | |
1010 | if (!s && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)) | |
1011 | range_on_entry (r, bb, name); | |
1012 | else | |
c25d317c | 1013 | range_of_expr (r, name, s); |
90e88fd3 | 1014 | gcc_checking_assert (r.undefined_p () |
6e02de94 | 1015 | || range_compatible_p (r.type (), TREE_TYPE (name))); |
90e88fd3 AM |
1016 | } |
1017 | ||
1018 | // Calculate a range for NAME on edge E and return it in R. | |
1019 | ||
1020 | bool | |
1021 | gimple_ranger::range_on_edge (irange &r, edge e, tree name) | |
1022 | { | |
1023 | int_range_max edge_range; | |
1024 | gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name))); | |
1025 | ||
1026 | // PHI arguments can be constants, catch these here. | |
1027 | if (!gimple_range_ssa_p (name)) | |
c25d317c | 1028 | return range_of_expr (r, name); |
90e88fd3 AM |
1029 | |
1030 | range_on_exit (r, e->src, name); | |
1031 | gcc_checking_assert (r.undefined_p () | |
6e02de94 | 1032 | || range_compatible_p (r.type(), TREE_TYPE (name))); |
90e88fd3 AM |
1033 | |
1034 | // Check to see if NAME is defined on edge e. | |
1035 | if (m_cache.outgoing_edge_range_p (edge_range, e, name)) | |
1036 | r.intersect (edge_range); | |
1037 | ||
1038 | return true; | |
1039 | } | |
1040 | ||
1041 | // Calculate a range for statement S and return it in R. If NAME is | |
1042 | // provided it represents the SSA_NAME on the LHS of the statement. | |
1043 | // It is only required if there is more than one lhs/output. Check | |
1044 | // the global cache for NAME first to see if the evaluation can be | |
c25d317c | 1045 | // avoided. If a range cannot be calculated, return false and UNDEFINED. |
90e88fd3 AM |
1046 | |
1047 | bool | |
1048 | gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) | |
1049 | { | |
c25d317c AM |
1050 | r.set_undefined (); |
1051 | ||
90e88fd3 AM |
1052 | if (!name) |
1053 | name = gimple_get_lhs (s); | |
1054 | ||
c25d317c | 1055 | // If no name, simply call the base routine. |
90e88fd3 AM |
1056 | if (!name) |
1057 | return calc_stmt (r, s, NULL_TREE); | |
1058 | ||
c25d317c AM |
1059 | if (!gimple_range_ssa_p (name)) |
1060 | return false; | |
90e88fd3 | 1061 | |
e86fd6a1 AM |
1062 | // Check if the stmt has already been processed, and is not stale. |
1063 | if (m_cache.get_non_stale_global_range (r, name)) | |
90e88fd3 | 1064 | return true; |
c25d317c | 1065 | |
129e1a8a AM |
1066 | // Otherwise calculate a new value. |
1067 | int_range_max tmp; | |
1068 | calc_stmt (tmp, s, name); | |
1069 | ||
1070 | // Combine the new value with the old value. This is required because | |
1071 | // the way value propagation works, when the IL changes on the fly we | |
1072 | // can sometimes get different results. See PR 97741. | |
1073 | r.intersect (tmp); | |
220929c0 | 1074 | m_cache.set_global_range (name, r); |
90e88fd3 AM |
1075 | return true; |
1076 | } | |
1077 | ||
1078 | // This routine will export whatever global ranges are known to GCC | |
1079 | // SSA_RANGE_NAME_INFO fields. | |
1080 | ||
1081 | void | |
1082 | gimple_ranger::export_global_ranges () | |
1083 | { | |
1084 | unsigned x; | |
1085 | int_range_max r; | |
1086 | if (dump_file) | |
1087 | { | |
1088 | fprintf (dump_file, "Exported global range table\n"); | |
1089 | fprintf (dump_file, "===========================\n"); | |
1090 | } | |
1091 | ||
1092 | for ( x = 1; x < num_ssa_names; x++) | |
1093 | { | |
1094 | tree name = ssa_name (x); | |
1095 | if (name && !SSA_NAME_IN_FREE_LIST (name) | |
1096 | && gimple_range_ssa_p (name) | |
220929c0 | 1097 | && m_cache.get_global_range (r, name) |
90e88fd3 AM |
1098 | && !r.varying_p()) |
1099 | { | |
1100 | // Make sure the new range is a subset of the old range. | |
1101 | int_range_max old_range; | |
1102 | old_range = gimple_range_global (name); | |
1103 | old_range.intersect (r); | |
1104 | /* Disable this while we fix tree-ssa/pr61743-2.c. */ | |
1105 | //gcc_checking_assert (old_range == r); | |
1106 | ||
1107 | // WTF? Can't write non-null pointer ranges?? stupid set_range_info! | |
1108 | if (!POINTER_TYPE_P (TREE_TYPE (name)) && !r.undefined_p ()) | |
1109 | { | |
1110 | value_range vr = r; | |
1111 | set_range_info (name, vr); | |
1112 | if (dump_file) | |
1113 | { | |
1114 | print_generic_expr (dump_file, name , TDF_SLIM); | |
1115 | fprintf (dump_file, " --> "); | |
1116 | vr.dump (dump_file); | |
1117 | fprintf (dump_file, "\n"); | |
1118 | fprintf (dump_file, " irange : "); | |
1119 | r.dump (dump_file); | |
1120 | fprintf (dump_file, "\n"); | |
1121 | } | |
1122 | } | |
1123 | } | |
1124 | } | |
1125 | } | |
1126 | ||
1127 | // Print the known table values to file F. | |
1128 | ||
1129 | void | |
1130 | gimple_ranger::dump (FILE *f) | |
1131 | { | |
1132 | basic_block bb; | |
1133 | ||
1134 | FOR_EACH_BB_FN (bb, cfun) | |
1135 | { | |
1136 | unsigned x; | |
1137 | edge_iterator ei; | |
1138 | edge e; | |
1139 | int_range_max range; | |
1140 | fprintf (f, "\n=========== BB %d ============\n", bb->index); | |
220929c0 | 1141 | m_cache.dump (f, bb); |
90e88fd3 AM |
1142 | |
1143 | dump_bb (f, bb, 4, TDF_NONE); | |
1144 | ||
1145 | // Now find any globals defined in this block. | |
1146 | for (x = 1; x < num_ssa_names; x++) | |
1147 | { | |
1148 | tree name = ssa_name (x); | |
1149 | if (gimple_range_ssa_p (name) && SSA_NAME_DEF_STMT (name) && | |
1150 | gimple_bb (SSA_NAME_DEF_STMT (name)) == bb && | |
220929c0 | 1151 | m_cache.get_global_range (range, name)) |
90e88fd3 AM |
1152 | { |
1153 | if (!range.varying_p ()) | |
1154 | { | |
1155 | print_generic_expr (f, name, TDF_SLIM); | |
1156 | fprintf (f, " : "); | |
1157 | range.dump (f); | |
1158 | fprintf (f, "\n"); | |
1159 | } | |
1160 | ||
1161 | } | |
1162 | } | |
1163 | ||
1164 | // And now outgoing edges, if they define anything. | |
1165 | FOR_EACH_EDGE (e, ei, bb->succs) | |
1166 | { | |
1167 | for (x = 1; x < num_ssa_names; x++) | |
1168 | { | |
1169 | tree name = gimple_range_ssa_p (ssa_name (x)); | |
1170 | if (name && m_cache.outgoing_edge_range_p (range, e, name)) | |
1171 | { | |
1172 | gimple *s = SSA_NAME_DEF_STMT (name); | |
1173 | // Only print the range if this is the def block, or | |
1174 | // the on entry cache for either end of the edge is | |
1175 | // set. | |
1176 | if ((s && bb == gimple_bb (s)) || | |
1177 | m_cache.block_range (range, bb, name, false) || | |
1178 | m_cache.block_range (range, e->dest, name, false)) | |
1179 | { | |
1180 | range_on_edge (range, e, name); | |
1181 | if (!range.varying_p ()) | |
1182 | { | |
1183 | fprintf (f, "%d->%d ", e->src->index, | |
1184 | e->dest->index); | |
1185 | char c = ' '; | |
1186 | if (e->flags & EDGE_TRUE_VALUE) | |
1187 | fprintf (f, " (T)%c", c); | |
1188 | else if (e->flags & EDGE_FALSE_VALUE) | |
1189 | fprintf (f, " (F)%c", c); | |
1190 | else | |
1191 | fprintf (f, " "); | |
1192 | print_generic_expr (f, name, TDF_SLIM); | |
1193 | fprintf(f, " : \t"); | |
1194 | range.dump(f); | |
1195 | fprintf (f, "\n"); | |
1196 | } | |
1197 | } | |
1198 | } | |
1199 | } | |
1200 | } | |
1201 | } | |
1202 | ||
220929c0 | 1203 | m_cache.dump (dump_file, (dump_flags & TDF_DETAILS) != 0); |
90e88fd3 AM |
1204 | } |
1205 | ||
1206 | // If SCEV has any information about phi node NAME, return it as a range in R. | |
1207 | ||
1208 | void | |
1209 | gimple_ranger::range_of_ssa_name_with_loop_info (irange &r, tree name, | |
1210 | class loop *l, gphi *phi) | |
1211 | { | |
1212 | gcc_checking_assert (TREE_CODE (name) == SSA_NAME); | |
1213 | tree min, max, type = TREE_TYPE (name); | |
1214 | if (bounds_of_var_in_loop (&min, &max, this, l, phi, name)) | |
1215 | { | |
1216 | // ?? We could do better here. Since MIN/MAX can only be an | |
1217 | // SSA, SSA +- INTEGER_CST, or INTEGER_CST, we could easily call | |
1218 | // the ranger and solve anything not an integer. | |
878315ae | 1219 | if (TREE_CODE (min) != INTEGER_CST) |
90e88fd3 | 1220 | min = vrp_val_min (type); |
878315ae | 1221 | if (TREE_CODE (max) != INTEGER_CST) |
90e88fd3 AM |
1222 | max = vrp_val_max (type); |
1223 | r.set (min, max); | |
1224 | } | |
1225 | else | |
1226 | r.set_varying (type); | |
1227 | } | |
1228 | ||
1229 | // -------------------------------------------------------------------------- | |
1230 | // trace_ranger implementation. | |
1231 | ||
1232 | ||
1233 | trace_ranger::trace_ranger () | |
1234 | { | |
1235 | indent = 0; | |
1236 | trace_count = 0; | |
1237 | } | |
1238 | ||
1239 | // If dumping, return true and print the prefix for the next output line. | |
1240 | ||
1241 | bool | |
1242 | trace_ranger::dumping (unsigned counter, bool trailing) | |
1243 | { | |
1244 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1245 | { | |
1246 | // Print counter index as well as INDENT spaces. | |
1247 | if (!trailing) | |
1248 | fprintf (dump_file, " %-7u ", counter); | |
1249 | else | |
1250 | fprintf (dump_file, " "); | |
1251 | unsigned x; | |
1252 | for (x = 0; x< indent; x++) | |
1253 | fputc (' ', dump_file); | |
1254 | return true; | |
1255 | } | |
1256 | return false; | |
1257 | } | |
1258 | ||
1259 | // After calling a routine, if dumping, print the CALLER, NAME, and RESULT, | |
1260 | // returning RESULT. | |
1261 | ||
1262 | bool | |
1263 | trace_ranger::trailer (unsigned counter, const char *caller, bool result, | |
1264 | tree name, const irange &r) | |
1265 | { | |
1266 | if (dumping (counter, true)) | |
1267 | { | |
1268 | indent -= bump; | |
1269 | fputs(result ? "TRUE : " : "FALSE : ", dump_file); | |
1270 | fprintf (dump_file, "(%u) ", counter); | |
1271 | fputs (caller, dump_file); | |
1272 | fputs (" (",dump_file); | |
1273 | if (name) | |
1274 | print_generic_expr (dump_file, name, TDF_SLIM); | |
1275 | fputs (") ",dump_file); | |
1276 | if (result) | |
1277 | { | |
1278 | r.dump (dump_file); | |
1279 | fputc('\n', dump_file); | |
1280 | } | |
1281 | else | |
1282 | fputc('\n', dump_file); | |
1283 | // Marks the end of a request. | |
1284 | if (indent == 0) | |
1285 | fputc('\n', dump_file); | |
1286 | } | |
1287 | return result; | |
1288 | } | |
1289 | ||
1290 | // Tracing version of range_on_edge. Call it with printing wrappers. | |
1291 | ||
1292 | bool | |
1293 | trace_ranger::range_on_edge (irange &r, edge e, tree name) | |
1294 | { | |
1295 | unsigned idx = ++trace_count; | |
1296 | if (dumping (idx)) | |
1297 | { | |
1298 | fprintf (dump_file, "range_on_edge ("); | |
1299 | print_generic_expr (dump_file, name, TDF_SLIM); | |
1300 | fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index); | |
1301 | indent += bump; | |
1302 | } | |
1303 | ||
1304 | bool res = gimple_ranger::range_on_edge (r, e, name); | |
1305 | trailer (idx, "range_on_edge", true, name, r); | |
1306 | return res; | |
1307 | } | |
1308 | ||
1309 | // Tracing version of range_on_entry. Call it with printing wrappers. | |
1310 | ||
1311 | void | |
1312 | trace_ranger::range_on_entry (irange &r, basic_block bb, tree name) | |
1313 | { | |
1314 | unsigned idx = ++trace_count; | |
1315 | if (dumping (idx)) | |
1316 | { | |
1317 | fprintf (dump_file, "range_on_entry ("); | |
1318 | print_generic_expr (dump_file, name, TDF_SLIM); | |
1319 | fprintf (dump_file, ") to BB %d\n", bb->index); | |
1320 | indent += bump; | |
1321 | } | |
1322 | ||
1323 | gimple_ranger::range_on_entry (r, bb, name); | |
1324 | ||
1325 | trailer (idx, "range_on_entry", true, name, r); | |
1326 | } | |
1327 | ||
1328 | // Tracing version of range_on_exit. Call it with printing wrappers. | |
1329 | ||
1330 | void | |
1331 | trace_ranger::range_on_exit (irange &r, basic_block bb, tree name) | |
1332 | { | |
1333 | unsigned idx = ++trace_count; | |
1334 | if (dumping (idx)) | |
1335 | { | |
1336 | fprintf (dump_file, "range_on_exit ("); | |
1337 | print_generic_expr (dump_file, name, TDF_SLIM); | |
1338 | fprintf (dump_file, ") from BB %d\n", bb->index); | |
1339 | indent += bump; | |
1340 | } | |
1341 | ||
1342 | gimple_ranger::range_on_exit (r, bb, name); | |
1343 | ||
1344 | trailer (idx, "range_on_exit", true, name, r); | |
1345 | } | |
1346 | ||
1347 | // Tracing version of range_of_stmt. Call it with printing wrappers. | |
1348 | ||
1349 | bool | |
1350 | trace_ranger::range_of_stmt (irange &r, gimple *s, tree name) | |
1351 | { | |
1352 | bool res; | |
1353 | unsigned idx = ++trace_count; | |
1354 | if (dumping (idx)) | |
1355 | { | |
1356 | fprintf (dump_file, "range_of_stmt ("); | |
1357 | if (name) | |
1358 | print_generic_expr (dump_file, name, TDF_SLIM); | |
1359 | fputs (") at stmt ", dump_file); | |
1360 | print_gimple_stmt (dump_file, s, 0, TDF_SLIM); | |
1361 | indent += bump; | |
1362 | } | |
1363 | ||
1364 | res = gimple_ranger::range_of_stmt (r, s, name); | |
1365 | ||
1366 | return trailer (idx, "range_of_stmt", res, name, r); | |
1367 | } | |
1368 | ||
1369 | // Tracing version of range_of_expr. Call it with printing wrappers. | |
1370 | ||
1371 | bool | |
1372 | trace_ranger::range_of_expr (irange &r, tree name, gimple *s) | |
1373 | { | |
1374 | bool res; | |
1375 | unsigned idx = ++trace_count; | |
1376 | if (dumping (idx)) | |
1377 | { | |
1378 | fprintf (dump_file, "range_of_expr("); | |
1379 | print_generic_expr (dump_file, name, TDF_SLIM); | |
1380 | fputs (")", dump_file); | |
1381 | if (s) | |
1382 | { | |
1383 | fputs (" at stmt ", dump_file); | |
1384 | print_gimple_stmt (dump_file, s, 0, TDF_SLIM); | |
1385 | } | |
1386 | else | |
1387 | fputs ("\n", dump_file); | |
1388 | indent += bump; | |
1389 | } | |
1390 | ||
1391 | res = gimple_ranger::range_of_expr (r, name, s); | |
1392 | ||
1393 | return trailer (idx, "range_of_expr", res, name, r); | |
1394 | } |