]>
Commit | Line | Data |
---|---|---|
51ce0638 AM |
1 | /* Code for GIMPLE range op related routines. |
2 | Copyright (C) 2019-2022 Free Software Foundation, Inc. | |
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 "tree.h" | |
28 | #include "gimple.h" | |
29 | #include "ssa.h" | |
30 | #include "gimple-pretty-print.h" | |
31 | #include "optabs-tree.h" | |
32 | #include "gimple-iterator.h" | |
33 | #include "gimple-fold.h" | |
34 | #include "wide-int.h" | |
35 | #include "fold-const.h" | |
36 | #include "case-cfn-macros.h" | |
37 | #include "omp-general.h" | |
38 | #include "cfgloop.h" | |
39 | #include "tree-ssa-loop.h" | |
40 | #include "tree-scalar-evolution.h" | |
41 | #include "langhooks.h" | |
42 | #include "vr-values.h" | |
43 | #include "range.h" | |
44 | #include "value-query.h" | |
45 | #include "gimple-range.h" | |
46 | ||
47 | // Given stmt S, fill VEC, up to VEC_SIZE elements, with relevant ssa-names | |
48 | // on the statement. For efficiency, it is an error to not pass in enough | |
49 | // elements for the vector. Return the number of ssa-names. | |
50 | ||
51 | unsigned | |
52 | gimple_range_ssa_names (tree *vec, unsigned vec_size, gimple *stmt) | |
53 | { | |
54 | tree ssa; | |
55 | int count = 0; | |
56 | ||
57 | gimple_range_op_handler handler (stmt); | |
58 | if (handler) | |
59 | { | |
60 | gcc_checking_assert (vec_size >= 2); | |
61 | if ((ssa = gimple_range_ssa_p (handler.operand1 ()))) | |
62 | vec[count++] = ssa; | |
63 | if ((ssa = gimple_range_ssa_p (handler.operand2 ()))) | |
64 | vec[count++] = ssa; | |
65 | } | |
66 | else if (is_a<gassign *> (stmt) | |
67 | && gimple_assign_rhs_code (stmt) == COND_EXPR) | |
68 | { | |
69 | gcc_checking_assert (vec_size >= 3); | |
70 | gassign *st = as_a<gassign *> (stmt); | |
71 | if ((ssa = gimple_range_ssa_p (gimple_assign_rhs1 (st)))) | |
72 | vec[count++] = ssa; | |
73 | if ((ssa = gimple_range_ssa_p (gimple_assign_rhs2 (st)))) | |
74 | vec[count++] = ssa; | |
75 | if ((ssa = gimple_range_ssa_p (gimple_assign_rhs3 (st)))) | |
76 | vec[count++] = ssa; | |
77 | } | |
78 | return count; | |
79 | } | |
80 | ||
81 | // Return the base of the RHS of an assignment. | |
82 | ||
83 | static tree | |
84 | gimple_range_base_of_assignment (const gimple *stmt) | |
85 | { | |
86 | gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN); | |
87 | tree op1 = gimple_assign_rhs1 (stmt); | |
88 | if (gimple_assign_rhs_code (stmt) == ADDR_EXPR) | |
89 | return get_base_address (TREE_OPERAND (op1, 0)); | |
90 | return op1; | |
91 | } | |
92 | ||
93 | // If statement is supported by range-ops, set the CODE and return the TYPE. | |
94 | ||
95 | static tree | |
96 | get_code_and_type (gimple *s, enum tree_code &code) | |
97 | { | |
98 | tree type = NULL_TREE; | |
99 | code = NOP_EXPR; | |
100 | ||
101 | if (const gassign *ass = dyn_cast<const gassign *> (s)) | |
102 | { | |
103 | code = gimple_assign_rhs_code (ass); | |
104 | // The LHS of a comparison is always an int, so we must look at | |
105 | // the operands. | |
106 | if (TREE_CODE_CLASS (code) == tcc_comparison) | |
107 | type = TREE_TYPE (gimple_assign_rhs1 (ass)); | |
108 | else | |
109 | type = TREE_TYPE (gimple_assign_lhs (ass)); | |
110 | } | |
111 | else if (const gcond *cond = dyn_cast<const gcond *> (s)) | |
112 | { | |
113 | code = gimple_cond_code (cond); | |
114 | type = TREE_TYPE (gimple_cond_lhs (cond)); | |
115 | } | |
116 | return type; | |
117 | } | |
118 | ||
119 | // If statement S has a supported range_op handler return TRUE. | |
120 | ||
121 | bool | |
122 | gimple_range_op_handler::supported_p (gimple *s) | |
123 | { | |
124 | enum tree_code code; | |
125 | tree type = get_code_and_type (s, code); | |
b40b3035 AM |
126 | if (type && range_op_handler (code, type)) |
127 | return true; | |
128 | if (is_a <gcall *> (s) && gimple_range_op_handler (s)) | |
129 | return true; | |
130 | return false; | |
51ce0638 AM |
131 | } |
132 | ||
133 | // Construct a handler object for statement S. | |
134 | ||
135 | gimple_range_op_handler::gimple_range_op_handler (gimple *s) | |
136 | { | |
137 | enum tree_code code; | |
138 | tree type = get_code_and_type (s, code); | |
139 | m_stmt = s; | |
b40b3035 AM |
140 | m_op1 = NULL_TREE; |
141 | m_op2 = NULL_TREE; | |
51ce0638 AM |
142 | if (type) |
143 | set_op_handler (code, type); | |
144 | ||
145 | if (m_valid) | |
146 | switch (gimple_code (m_stmt)) | |
147 | { | |
148 | case GIMPLE_COND: | |
149 | m_op1 = gimple_cond_lhs (m_stmt); | |
150 | m_op2 = gimple_cond_rhs (m_stmt); | |
b40b3035 | 151 | return; |
51ce0638 AM |
152 | case GIMPLE_ASSIGN: |
153 | m_op1 = gimple_range_base_of_assignment (m_stmt); | |
154 | if (m_op1 && TREE_CODE (m_op1) == MEM_REF) | |
155 | { | |
156 | // If the base address is an SSA_NAME, we return it | |
157 | // here. This allows processing of the range of that | |
158 | // name, while the rest of the expression is simply | |
159 | // ignored. The code in range_ops will see the | |
160 | // ADDR_EXPR and do the right thing. | |
161 | tree ssa = TREE_OPERAND (m_op1, 0); | |
162 | if (TREE_CODE (ssa) == SSA_NAME) | |
163 | m_op1 = ssa; | |
164 | } | |
165 | if (gimple_num_ops (m_stmt) >= 3) | |
166 | m_op2 = gimple_assign_rhs2 (m_stmt); | |
b40b3035 | 167 | return; |
51ce0638 | 168 | default: |
b40b3035 AM |
169 | gcc_unreachable (); |
170 | return; | |
51ce0638 | 171 | } |
b40b3035 AM |
172 | // If no range-op table entry handled this stmt, check for other supported |
173 | // statements. | |
174 | if (is_a <gcall *> (m_stmt)) | |
175 | maybe_builtin_call (); | |
51ce0638 AM |
176 | } |
177 | ||
178 | // Calculate what we can determine of the range of this unary | |
179 | // statement's operand if the lhs of the expression has the range | |
180 | // LHS_RANGE. Return false if nothing can be determined. | |
181 | ||
182 | bool | |
183 | gimple_range_op_handler::calc_op1 (vrange &r, const vrange &lhs_range) | |
184 | { | |
185 | gcc_checking_assert (gimple_num_ops (m_stmt) < 3); | |
186 | // Give up on empty ranges. | |
187 | if (lhs_range.undefined_p ()) | |
188 | return false; | |
189 | ||
190 | // Unary operations require the type of the first operand in the | |
191 | // second range position. | |
192 | tree type = TREE_TYPE (operand1 ()); | |
193 | Value_Range type_range (type); | |
194 | type_range.set_varying (type); | |
195 | return op1_range (r, type, lhs_range, type_range); | |
196 | } | |
197 | ||
198 | // Calculate what we can determine of the range of this statement's | |
199 | // first operand if the lhs of the expression has the range LHS_RANGE | |
200 | // and the second operand has the range OP2_RANGE. Return false if | |
201 | // nothing can be determined. | |
202 | ||
203 | bool | |
204 | gimple_range_op_handler::calc_op1 (vrange &r, const vrange &lhs_range, | |
431cdfbe | 205 | const vrange &op2_range, relation_kind k) |
51ce0638 AM |
206 | { |
207 | // Give up on empty ranges. | |
208 | if (lhs_range.undefined_p ()) | |
209 | return false; | |
210 | ||
211 | // Unary operation are allowed to pass a range in for second operand | |
212 | // as there are often additional restrictions beyond the type which | |
213 | // can be imposed. See operator_cast::op1_range(). | |
214 | tree type = TREE_TYPE (operand1 ()); | |
215 | // If op2 is undefined, solve as if it is varying. | |
216 | if (op2_range.undefined_p ()) | |
217 | { | |
51ce0638 AM |
218 | if (gimple_num_ops (m_stmt) < 3) |
219 | return false; | |
a7a6649f AM |
220 | tree op2_type; |
221 | // This is sometimes invoked on single operand stmts. | |
222 | if (operand2 ()) | |
223 | op2_type = TREE_TYPE (operand2 ()); | |
224 | else | |
225 | op2_type = TREE_TYPE (operand1 ()); | |
51ce0638 AM |
226 | Value_Range trange (op2_type); |
227 | trange.set_varying (op2_type); | |
431cdfbe | 228 | return op1_range (r, type, lhs_range, trange, k); |
51ce0638 | 229 | } |
431cdfbe | 230 | return op1_range (r, type, lhs_range, op2_range, k); |
51ce0638 AM |
231 | } |
232 | ||
233 | // Calculate what we can determine of the range of this statement's | |
234 | // second operand if the lhs of the expression has the range LHS_RANGE | |
235 | // and the first operand has the range OP1_RANGE. Return false if | |
236 | // nothing can be determined. | |
237 | ||
238 | bool | |
239 | gimple_range_op_handler::calc_op2 (vrange &r, const vrange &lhs_range, | |
431cdfbe | 240 | const vrange &op1_range, relation_kind k) |
51ce0638 AM |
241 | { |
242 | // Give up on empty ranges. | |
243 | if (lhs_range.undefined_p ()) | |
244 | return false; | |
245 | ||
246 | tree type = TREE_TYPE (operand2 ()); | |
247 | // If op1 is undefined, solve as if it is varying. | |
248 | if (op1_range.undefined_p ()) | |
249 | { | |
250 | tree op1_type = TREE_TYPE (operand1 ()); | |
251 | Value_Range trange (op1_type); | |
252 | trange.set_varying (op1_type); | |
431cdfbe | 253 | return op2_range (r, type, lhs_range, trange, k); |
51ce0638 | 254 | } |
431cdfbe | 255 | return op2_range (r, type, lhs_range, op1_range, k); |
51ce0638 | 256 | } |
b40b3035 AM |
257 | |
258 | // -------------------------------------------------------------------- | |
259 | ||
260 | // Implement range operator for float CFN_BUILT_IN_CONSTANT_P. | |
261 | class cfn_constant_float_p : public range_operator_float | |
262 | { | |
263 | public: | |
264 | using range_operator_float::fold_range; | |
265 | virtual bool fold_range (irange &r, tree type, const frange &lh, | |
266 | const irange &, relation_kind) const | |
267 | { | |
268 | if (lh.singleton_p ()) | |
269 | { | |
270 | r.set (build_one_cst (type), build_one_cst (type)); | |
271 | return true; | |
272 | } | |
273 | if (cfun->after_inlining) | |
274 | { | |
275 | r.set_zero (type); | |
276 | return true; | |
277 | } | |
278 | return false; | |
279 | } | |
280 | } op_cfn_constant_float_p; | |
281 | ||
282 | // Implement range operator for integral CFN_BUILT_IN_CONSTANT_P. | |
283 | class cfn_constant_p : public range_operator | |
284 | { | |
285 | public: | |
286 | using range_operator::fold_range; | |
287 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
288 | const irange &, relation_kind) const | |
289 | { | |
290 | if (lh.singleton_p ()) | |
291 | { | |
292 | r.set (build_one_cst (type), build_one_cst (type)); | |
293 | return true; | |
294 | } | |
295 | if (cfun->after_inlining) | |
296 | { | |
297 | r.set_zero (type); | |
298 | return true; | |
299 | } | |
300 | return false; | |
301 | } | |
302 | } op_cfn_constant_p; | |
303 | ||
eb82b9f6 AM |
304 | // Implement range operator for CFN_BUILT_IN_SIGNBIT. |
305 | class cfn_signbit : public range_operator_float | |
306 | { | |
307 | public: | |
308 | using range_operator_float::fold_range; | |
98ad4527 | 309 | using range_operator_float::op1_range; |
eb82b9f6 | 310 | virtual bool fold_range (irange &r, tree type, const frange &lh, |
70d81e3a | 311 | const irange &, relation_kind) const override |
eb82b9f6 AM |
312 | { |
313 | bool signbit; | |
314 | if (lh.signbit_p (signbit)) | |
315 | { | |
316 | if (signbit) | |
317 | r.set_nonzero (type); | |
318 | else | |
319 | r.set_zero (type); | |
320 | return true; | |
321 | } | |
322 | return false; | |
323 | } | |
98ad4527 AH |
324 | virtual bool op1_range (frange &r, tree type, const irange &lhs, |
325 | const frange &, relation_kind) const override | |
326 | { | |
327 | if (lhs.zero_p ()) | |
328 | { | |
329 | r.set (type, dconst0, frange_val_max (type)); | |
330 | r.update_nan (false); | |
331 | return true; | |
332 | } | |
333 | if (!lhs.contains_p (build_zero_cst (lhs.type ()))) | |
334 | { | |
335 | REAL_VALUE_TYPE dconstm0 = dconst0; | |
336 | dconstm0.sign = 1; | |
337 | r.set (type, frange_val_min (type), dconstm0); | |
338 | r.update_nan (true); | |
339 | return true; | |
340 | } | |
341 | return false; | |
342 | } | |
eb82b9f6 AM |
343 | } op_cfn_signbit; |
344 | ||
8efc3834 AH |
345 | // Implement range operator for CFN_BUILT_IN_COPYSIGN |
346 | class cfn_copysign : public range_operator_float | |
347 | { | |
348 | public: | |
349 | using range_operator_float::fold_range; | |
350 | virtual bool fold_range (frange &r, tree type, const frange &lh, | |
351 | const frange &rh, relation_kind) const override | |
352 | { | |
353 | frange neg; | |
354 | range_op_handler abs_op (ABS_EXPR, type); | |
355 | range_op_handler neg_op (NEGATE_EXPR, type); | |
356 | if (!abs_op || !abs_op.fold_range (r, type, lh, frange (type))) | |
357 | return false; | |
358 | if (!neg_op || !neg_op.fold_range (neg, type, r, frange (type))) | |
359 | return false; | |
360 | ||
361 | bool signbit; | |
362 | if (rh.signbit_p (signbit)) | |
363 | { | |
364 | // If the sign is negative, flip the result from ABS, | |
365 | // otherwise leave things positive. | |
366 | if (signbit) | |
367 | r = neg; | |
368 | } | |
369 | else | |
370 | // If the sign is unknown, keep the positive and negative | |
371 | // alternatives. | |
372 | r.union_ (neg); | |
373 | return true; | |
374 | } | |
375 | } op_cfn_copysign; | |
376 | ||
2f5da730 AM |
377 | // Implement range operator for CFN_BUILT_IN_TOUPPER and CFN_BUILT_IN_TOLOWER. |
378 | class cfn_toupper_tolower : public range_operator | |
379 | { | |
380 | public: | |
381 | using range_operator::fold_range; | |
382 | cfn_toupper_tolower (bool toupper) { m_toupper = toupper; } | |
383 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
384 | const irange &, relation_kind) const; | |
385 | private: | |
386 | bool get_letter_range (tree type, irange &lowers, irange &uppers) const; | |
387 | bool m_toupper; | |
388 | } op_cfn_toupper (true), op_cfn_tolower (false); | |
389 | ||
390 | // Return TRUE if we recognize the target character set and return the | |
391 | // range for lower case and upper case letters. | |
392 | ||
393 | bool | |
394 | cfn_toupper_tolower::get_letter_range (tree type, irange &lowers, | |
395 | irange &uppers) const | |
396 | { | |
397 | // ASCII | |
398 | int a = lang_hooks.to_target_charset ('a'); | |
399 | int z = lang_hooks.to_target_charset ('z'); | |
400 | int A = lang_hooks.to_target_charset ('A'); | |
401 | int Z = lang_hooks.to_target_charset ('Z'); | |
402 | ||
403 | if ((z - a == 25) && (Z - A == 25)) | |
404 | { | |
405 | lowers = int_range<2> (build_int_cst (type, a), build_int_cst (type, z)); | |
406 | uppers = int_range<2> (build_int_cst (type, A), build_int_cst (type, Z)); | |
407 | return true; | |
408 | } | |
409 | // Unknown character set. | |
410 | return false; | |
411 | } | |
412 | ||
413 | bool | |
414 | cfn_toupper_tolower::fold_range (irange &r, tree type, const irange &lh, | |
415 | const irange &, relation_kind) const | |
416 | { | |
417 | int_range<3> lowers; | |
418 | int_range<3> uppers; | |
419 | if (!get_letter_range (type, lowers, uppers)) | |
420 | return false; | |
421 | ||
422 | r = lh; | |
423 | if (m_toupper) | |
424 | { | |
425 | // Return the range passed in without any lower case characters, | |
426 | // but including all the upper case ones. | |
427 | lowers.invert (); | |
428 | r.intersect (lowers); | |
429 | r.union_ (uppers); | |
430 | } | |
431 | else | |
432 | { | |
433 | // Return the range passed in without any lower case characters, | |
434 | // but including all the upper case ones. | |
435 | uppers.invert (); | |
436 | r.intersect (uppers); | |
437 | r.union_ (lowers); | |
438 | } | |
439 | return true; | |
440 | } | |
441 | ||
f50d1031 AH |
442 | // Implement range operator for CFN_BUILT_IN_FFS. |
443 | class cfn_ffs : public range_operator | |
5f730c65 AM |
444 | { |
445 | public: | |
446 | using range_operator::fold_range; | |
447 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
448 | const irange &, relation_kind) const | |
449 | { | |
450 | if (lh.undefined_p ()) | |
451 | return false; | |
452 | // __builtin_ffs* and __builtin_popcount* return [0, prec]. | |
453 | int prec = TYPE_PRECISION (lh.type ()); | |
454 | // If arg is non-zero, then ffs or popcount are non-zero. | |
455 | int mini = range_includes_zero_p (&lh) ? 0 : 1; | |
456 | int maxi = prec; | |
457 | ||
458 | // If some high bits are known to be zero, decrease the maximum. | |
459 | int_range_max tmp = lh; | |
460 | if (TYPE_SIGN (tmp.type ()) == SIGNED) | |
461 | range_cast (tmp, unsigned_type_for (tmp.type ())); | |
462 | wide_int max = tmp.upper_bound (); | |
463 | maxi = wi::floor_log2 (max) + 1; | |
464 | r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); | |
465 | return true; | |
466 | } | |
f50d1031 AH |
467 | } op_cfn_ffs; |
468 | ||
469 | // Implement range operator for CFN_BUILT_IN_POPCOUNT. | |
470 | class cfn_popcount : public cfn_ffs | |
471 | { | |
472 | public: | |
473 | using range_operator::fold_range; | |
474 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
475 | const irange &rh, relation_kind rel) const | |
476 | { | |
4c451631 AH |
477 | if (lh.undefined_p ()) |
478 | return false; | |
479 | unsigned prec = TYPE_PRECISION (type); | |
480 | wide_int nz = lh.get_nonzero_bits (); | |
481 | wide_int pop = wi::shwi (wi::popcount (nz), prec); | |
f50d1031 AH |
482 | // Calculating the popcount of a singleton is trivial. |
483 | if (lh.singleton_p ()) | |
484 | { | |
f50d1031 AH |
485 | r.set (type, pop, pop); |
486 | return true; | |
487 | } | |
4c451631 AH |
488 | if (cfn_ffs::fold_range (r, type, lh, rh, rel)) |
489 | { | |
490 | int_range<2> tmp (type, wi::zero (prec), pop); | |
491 | r.intersect (tmp); | |
492 | return true; | |
493 | } | |
494 | return false; | |
f50d1031 | 495 | } |
5f730c65 AM |
496 | } op_cfn_popcount; |
497 | ||
ae1669a9 AM |
498 | // Implement range operator for CFN_BUILT_IN_CLZ |
499 | class cfn_clz : public range_operator | |
500 | { | |
501 | public: | |
502 | cfn_clz (bool internal) { m_gimple_call_internal_p = internal; } | |
503 | using range_operator::fold_range; | |
504 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
505 | const irange &, relation_kind) const; | |
506 | private: | |
507 | bool m_gimple_call_internal_p; | |
508 | } op_cfn_clz (false), op_cfn_clz_internal (true); | |
509 | ||
510 | bool | |
511 | cfn_clz::fold_range (irange &r, tree type, const irange &lh, | |
512 | const irange &, relation_kind) const | |
513 | { | |
514 | // __builtin_c[lt]z* return [0, prec-1], except when the | |
515 | // argument is 0, but that is undefined behavior. | |
516 | // | |
517 | // For __builtin_c[lt]z* consider argument of 0 always undefined | |
518 | // behavior, for internal fns depending on C?Z_DEFINED_ALUE_AT_ZERO. | |
519 | if (lh.undefined_p ()) | |
520 | return false; | |
521 | int prec = TYPE_PRECISION (lh.type ()); | |
522 | int mini = 0; | |
523 | int maxi = prec - 1; | |
524 | int zerov = 0; | |
525 | scalar_int_mode mode = SCALAR_INT_TYPE_MODE (lh.type ()); | |
526 | if (m_gimple_call_internal_p) | |
527 | { | |
528 | if (optab_handler (clz_optab, mode) != CODE_FOR_nothing | |
529 | && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov) == 2) | |
530 | { | |
531 | // Only handle the single common value. | |
532 | if (zerov == prec) | |
533 | maxi = prec; | |
534 | else | |
535 | // Magic value to give up, unless we can prove arg is non-zero. | |
536 | mini = -2; | |
537 | } | |
538 | } | |
539 | ||
540 | // From clz of minimum we can compute result maximum. | |
541 | if (wi::gt_p (lh.lower_bound (), 0, TYPE_SIGN (lh.type ()))) | |
542 | { | |
543 | maxi = prec - 1 - wi::floor_log2 (lh.lower_bound ()); | |
544 | if (mini == -2) | |
545 | mini = 0; | |
546 | } | |
547 | else if (!range_includes_zero_p (&lh)) | |
548 | { | |
549 | mini = 0; | |
550 | maxi = prec - 1; | |
551 | } | |
552 | if (mini == -2) | |
553 | return false; | |
554 | // From clz of maximum we can compute result minimum. | |
555 | wide_int max = lh.upper_bound (); | |
556 | int newmini = prec - 1 - wi::floor_log2 (max); | |
557 | if (max == 0) | |
558 | { | |
559 | // If CLZ_DEFINED_VALUE_AT_ZERO is 2 with VALUE of prec, | |
560 | // return [prec, prec], otherwise ignore the range. | |
561 | if (maxi == prec) | |
562 | mini = prec; | |
563 | } | |
564 | else | |
565 | mini = newmini; | |
566 | ||
567 | if (mini == -2) | |
568 | return false; | |
569 | r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); | |
570 | return true; | |
571 | } | |
572 | ||
55738d8d AM |
573 | // Implement range operator for CFN_BUILT_IN_CTZ |
574 | class cfn_ctz : public range_operator | |
575 | { | |
576 | public: | |
577 | cfn_ctz (bool internal) { m_gimple_call_internal_p = internal; } | |
578 | using range_operator::fold_range; | |
579 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
580 | const irange &, relation_kind) const; | |
581 | private: | |
582 | bool m_gimple_call_internal_p; | |
583 | } op_cfn_ctz (false), op_cfn_ctz_internal (true); | |
584 | ||
585 | bool | |
586 | cfn_ctz::fold_range (irange &r, tree type, const irange &lh, | |
587 | const irange &, relation_kind) const | |
588 | { | |
589 | if (lh.undefined_p ()) | |
590 | return false; | |
591 | int prec = TYPE_PRECISION (lh.type ()); | |
592 | int mini = 0; | |
593 | int maxi = prec - 1; | |
594 | int zerov = 0; | |
595 | scalar_int_mode mode = SCALAR_INT_TYPE_MODE (lh.type ()); | |
596 | ||
597 | if (m_gimple_call_internal_p) | |
598 | { | |
599 | if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing | |
600 | && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov) == 2) | |
601 | { | |
602 | // Handle only the two common values. | |
603 | if (zerov == -1) | |
604 | mini = -1; | |
605 | else if (zerov == prec) | |
606 | maxi = prec; | |
607 | else | |
608 | // Magic value to give up, unless we can prove arg is non-zero. | |
609 | mini = -2; | |
610 | } | |
611 | } | |
612 | // If arg is non-zero, then use [0, prec - 1]. | |
613 | if (!range_includes_zero_p (&lh)) | |
614 | { | |
615 | mini = 0; | |
616 | maxi = prec - 1; | |
617 | } | |
618 | // If some high bits are known to be zero, we can decrease | |
619 | // the maximum. | |
620 | wide_int max = lh.upper_bound (); | |
621 | if (max == 0) | |
622 | { | |
623 | // Argument is [0, 0]. If CTZ_DEFINED_VALUE_AT_ZERO | |
624 | // is 2 with value -1 or prec, return [-1, -1] or [prec, prec]. | |
625 | // Otherwise ignore the range. | |
626 | if (mini == -1) | |
627 | maxi = -1; | |
628 | else if (maxi == prec) | |
629 | mini = prec; | |
630 | } | |
631 | // If value at zero is prec and 0 is in the range, we can't lower | |
632 | // the upper bound. We could create two separate ranges though, | |
633 | // [0,floor_log2(max)][prec,prec] though. | |
634 | else if (maxi != prec) | |
635 | maxi = wi::floor_log2 (max); | |
636 | ||
637 | if (mini == -2) | |
638 | return false; | |
639 | r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); | |
640 | return true; | |
641 | } | |
642 | ||
f7e62b09 AM |
643 | |
644 | // Implement range operator for CFN_BUILT_IN_ | |
645 | class cfn_clrsb : public range_operator | |
646 | { | |
647 | public: | |
648 | using range_operator::fold_range; | |
649 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
650 | const irange &, relation_kind) const | |
651 | { | |
652 | if (lh.undefined_p ()) | |
653 | return false; | |
654 | int prec = TYPE_PRECISION (lh.type ()); | |
655 | r.set (build_int_cst (type, 0), build_int_cst (type, prec - 1)); | |
656 | return true; | |
657 | } | |
658 | } op_cfn_clrsb; | |
659 | ||
b6f670ff AM |
660 | |
661 | // Implement range operator for CFN_BUILT_IN_ | |
662 | class cfn_ubsan : public range_operator | |
663 | { | |
664 | public: | |
665 | cfn_ubsan (enum tree_code code) { m_code = code; } | |
666 | using range_operator::fold_range; | |
667 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
668 | const irange &rh, relation_kind rel) const | |
669 | { | |
670 | range_op_handler handler (m_code, type); | |
671 | gcc_checking_assert (handler); | |
672 | ||
673 | bool saved_flag_wrapv = flag_wrapv; | |
674 | // Pretend the arithmetic is wrapping. If there is any overflow, | |
675 | // we'll complain, but will actually do wrapping operation. | |
676 | flag_wrapv = 1; | |
677 | bool result = handler.fold_range (r, type, lh, rh, rel); | |
678 | flag_wrapv = saved_flag_wrapv; | |
679 | ||
680 | // If for both arguments vrp_valueize returned non-NULL, this should | |
681 | // have been already folded and if not, it wasn't folded because of | |
682 | // overflow. Avoid removing the UBSAN_CHECK_* calls in that case. | |
683 | if (result && r.singleton_p ()) | |
684 | r.set_varying (type); | |
685 | return result; | |
686 | } | |
687 | private: | |
688 | enum tree_code m_code; | |
689 | }; | |
690 | ||
691 | cfn_ubsan op_cfn_ubsan_add (PLUS_EXPR); | |
692 | cfn_ubsan op_cfn_ubsan_sub (MINUS_EXPR); | |
693 | cfn_ubsan op_cfn_ubsan_mul (MULT_EXPR); | |
694 | ||
c750e675 AM |
695 | |
696 | // Implement range operator for CFN_BUILT_IN_STRLEN | |
697 | class cfn_strlen : public range_operator | |
698 | { | |
699 | public: | |
700 | using range_operator::fold_range; | |
701 | virtual bool fold_range (irange &r, tree type, const irange &, | |
702 | const irange &, relation_kind) const | |
703 | { | |
704 | tree max = vrp_val_max (ptrdiff_type_node); | |
705 | wide_int wmax | |
706 | = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); | |
707 | tree range_min = build_zero_cst (type); | |
708 | // To account for the terminating NULL, the maximum length | |
709 | // is one less than the maximum array size, which in turn | |
710 | // is one less than PTRDIFF_MAX (or SIZE_MAX where it's | |
711 | // smaller than the former type). | |
712 | // FIXME: Use max_object_size() - 1 here. | |
713 | tree range_max = wide_int_to_tree (type, wmax - 2); | |
714 | r.set (range_min, range_max); | |
715 | return true; | |
716 | } | |
717 | } op_cfn_strlen; | |
718 | ||
e7f035f6 AM |
719 | |
720 | // Implement range operator for CFN_BUILT_IN_GOACC_DIM | |
721 | class cfn_goacc_dim : public range_operator | |
722 | { | |
723 | public: | |
724 | cfn_goacc_dim (bool is_pos) { m_is_pos = is_pos; } | |
725 | using range_operator::fold_range; | |
726 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
727 | const irange &, relation_kind) const | |
728 | { | |
729 | tree axis_tree; | |
730 | if (!lh.singleton_p (&axis_tree)) | |
731 | return false; | |
732 | HOST_WIDE_INT axis = TREE_INT_CST_LOW (axis_tree); | |
733 | int size = oacc_get_fn_dim_size (current_function_decl, axis); | |
734 | if (!size) | |
735 | // If it's dynamic, the backend might know a hardware limitation. | |
736 | size = targetm.goacc.dim_limit (axis); | |
737 | ||
738 | r.set (build_int_cst (type, m_is_pos ? 0 : 1), | |
739 | size | |
740 | ? build_int_cst (type, size - m_is_pos) : vrp_val_max (type)); | |
741 | return true; | |
742 | } | |
743 | private: | |
744 | bool m_is_pos; | |
745 | } op_cfn_goacc_dim_size (false), op_cfn_goacc_dim_pos (true); | |
746 | ||
5608e410 AM |
747 | |
748 | // Implement range operator for CFN_BUILT_IN_ | |
749 | class cfn_parity : public range_operator | |
750 | { | |
751 | public: | |
752 | using range_operator::fold_range; | |
753 | virtual bool fold_range (irange &r, tree type, const irange &, | |
754 | const irange &, relation_kind) const | |
755 | { | |
756 | r.set (build_zero_cst (type), build_one_cst (type)); | |
757 | return true; | |
758 | } | |
759 | } op_cfn_parity; | |
760 | ||
b40b3035 AM |
761 | // Set up a gimple_range_op_handler for any built in function which can be |
762 | // supported via range-ops. | |
763 | ||
764 | void | |
765 | gimple_range_op_handler::maybe_builtin_call () | |
766 | { | |
767 | gcc_checking_assert (is_a <gcall *> (m_stmt)); | |
768 | ||
769 | gcall *call = as_a <gcall *> (m_stmt); | |
770 | combined_fn func = gimple_call_combined_fn (call); | |
771 | if (func == CFN_LAST) | |
772 | return; | |
773 | tree type = gimple_range_type (call); | |
774 | gcc_checking_assert (type); | |
775 | if (!Value_Range::supports_type_p (type)) | |
776 | return; | |
777 | ||
778 | switch (func) | |
779 | { | |
780 | case CFN_BUILT_IN_CONSTANT_P: | |
781 | m_op1 = gimple_call_arg (call, 0); | |
782 | m_valid = true; | |
783 | if (irange::supports_p (TREE_TYPE (m_op1))) | |
784 | m_int = &op_cfn_constant_p; | |
785 | else if (frange::supports_p (TREE_TYPE (m_op1))) | |
786 | m_float = &op_cfn_constant_float_p; | |
787 | else | |
788 | m_valid = false; | |
789 | break; | |
790 | ||
823e9097 | 791 | CASE_FLT_FN (CFN_BUILT_IN_SIGNBIT): |
eb82b9f6 AM |
792 | m_op1 = gimple_call_arg (call, 0); |
793 | m_float = &op_cfn_signbit; | |
794 | m_valid = true; | |
795 | break; | |
796 | ||
8efc3834 AH |
797 | CASE_CFN_COPYSIGN_ALL: |
798 | m_op1 = gimple_call_arg (call, 0); | |
799 | m_op2 = gimple_call_arg (call, 1); | |
800 | m_float = &op_cfn_copysign; | |
801 | m_valid = true; | |
802 | break; | |
803 | ||
2f5da730 AM |
804 | case CFN_BUILT_IN_TOUPPER: |
805 | case CFN_BUILT_IN_TOLOWER: | |
806 | // Only proceed If the argument is compatible with the LHS. | |
807 | m_op1 = gimple_call_arg (call, 0); | |
808 | if (range_compatible_p (type, TREE_TYPE (m_op1))) | |
809 | { | |
810 | m_valid = true; | |
811 | m_int = (func == CFN_BUILT_IN_TOLOWER) ? &op_cfn_tolower | |
812 | : &op_cfn_toupper; | |
813 | } | |
814 | break; | |
815 | ||
5f730c65 | 816 | CASE_CFN_FFS: |
f50d1031 AH |
817 | m_op1 = gimple_call_arg (call, 0); |
818 | m_int = &op_cfn_ffs; | |
819 | m_valid = true; | |
820 | break; | |
821 | ||
5f730c65 AM |
822 | CASE_CFN_POPCOUNT: |
823 | m_op1 = gimple_call_arg (call, 0); | |
824 | m_int = &op_cfn_popcount; | |
825 | m_valid = true; | |
826 | break; | |
827 | ||
ae1669a9 AM |
828 | CASE_CFN_CLZ: |
829 | m_op1 = gimple_call_arg (call, 0); | |
830 | m_valid = true; | |
831 | if (gimple_call_internal_p (call)) | |
832 | m_int = &op_cfn_clz_internal; | |
833 | else | |
834 | m_int = &op_cfn_clz; | |
835 | break; | |
836 | ||
55738d8d AM |
837 | CASE_CFN_CTZ: |
838 | m_op1 = gimple_call_arg (call, 0); | |
839 | m_valid = true; | |
840 | if (gimple_call_internal_p (call)) | |
841 | m_int = &op_cfn_ctz_internal; | |
842 | else | |
843 | m_int = &op_cfn_ctz; | |
844 | break; | |
845 | ||
f7e62b09 AM |
846 | CASE_CFN_CLRSB: |
847 | m_op1 = gimple_call_arg (call, 0); | |
848 | m_valid = true; | |
849 | m_int = &op_cfn_clrsb; | |
850 | break; | |
851 | ||
b6f670ff AM |
852 | case CFN_UBSAN_CHECK_ADD: |
853 | m_op1 = gimple_call_arg (call, 0); | |
854 | m_op2 = gimple_call_arg (call, 1); | |
855 | m_valid = true; | |
856 | m_int = &op_cfn_ubsan_add; | |
857 | break; | |
858 | ||
859 | case CFN_UBSAN_CHECK_SUB: | |
860 | m_op1 = gimple_call_arg (call, 0); | |
861 | m_op2 = gimple_call_arg (call, 1); | |
862 | m_valid = true; | |
863 | m_int = &op_cfn_ubsan_sub; | |
864 | break; | |
865 | ||
866 | case CFN_UBSAN_CHECK_MUL: | |
867 | m_op1 = gimple_call_arg (call, 0); | |
868 | m_op2 = gimple_call_arg (call, 1); | |
869 | m_valid = true; | |
870 | m_int = &op_cfn_ubsan_mul; | |
871 | break; | |
872 | ||
c750e675 AM |
873 | case CFN_BUILT_IN_STRLEN: |
874 | { | |
875 | tree lhs = gimple_call_lhs (call); | |
876 | if (lhs && ptrdiff_type_node && (TYPE_PRECISION (ptrdiff_type_node) | |
877 | == TYPE_PRECISION (TREE_TYPE (lhs)))) | |
878 | { | |
879 | m_op1 = gimple_call_arg (call, 0); | |
880 | m_valid = true; | |
881 | m_int = &op_cfn_strlen; | |
882 | } | |
883 | break; | |
884 | } | |
885 | ||
e7f035f6 AM |
886 | // Optimizing these two internal functions helps the loop |
887 | // optimizer eliminate outer comparisons. Size is [1,N] | |
888 | // and pos is [0,N-1]. | |
889 | case CFN_GOACC_DIM_SIZE: | |
890 | // This call will ensure all the asserts are triggered. | |
891 | oacc_get_ifn_dim_arg (call); | |
892 | m_op1 = gimple_call_arg (call, 0); | |
893 | m_valid = true; | |
894 | m_int = &op_cfn_goacc_dim_size; | |
895 | break; | |
896 | ||
897 | case CFN_GOACC_DIM_POS: | |
898 | // This call will ensure all the asserts are triggered. | |
899 | oacc_get_ifn_dim_arg (call); | |
900 | m_op1 = gimple_call_arg (call, 0); | |
901 | m_valid = true; | |
902 | m_int = &op_cfn_goacc_dim_pos; | |
903 | break; | |
904 | ||
5608e410 AM |
905 | CASE_CFN_PARITY: |
906 | m_valid = true; | |
907 | m_int = &op_cfn_parity; | |
908 | break; | |
909 | ||
b40b3035 AM |
910 | default: |
911 | break; | |
912 | } | |
913 | } |