]>
Commit | Line | Data |
---|---|---|
51ce0638 | 1 | /* Code for GIMPLE range op related routines. |
aeee4812 | 2 | Copyright (C) 2019-2023 Free Software Foundation, Inc. |
51ce0638 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 "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); | |
0ef9991d AM |
151 | // Check that operands are supported types. One check is enough. |
152 | if (!Value_Range::supports_type_p (TREE_TYPE (m_op1))) | |
153 | m_valid = false; | |
b40b3035 | 154 | return; |
51ce0638 AM |
155 | case GIMPLE_ASSIGN: |
156 | m_op1 = gimple_range_base_of_assignment (m_stmt); | |
157 | if (m_op1 && TREE_CODE (m_op1) == MEM_REF) | |
158 | { | |
159 | // If the base address is an SSA_NAME, we return it | |
160 | // here. This allows processing of the range of that | |
161 | // name, while the rest of the expression is simply | |
162 | // ignored. The code in range_ops will see the | |
163 | // ADDR_EXPR and do the right thing. | |
164 | tree ssa = TREE_OPERAND (m_op1, 0); | |
165 | if (TREE_CODE (ssa) == SSA_NAME) | |
166 | m_op1 = ssa; | |
167 | } | |
168 | if (gimple_num_ops (m_stmt) >= 3) | |
169 | m_op2 = gimple_assign_rhs2 (m_stmt); | |
0ef9991d AM |
170 | // Check that operands are supported types. One check is enough. |
171 | if ((m_op1 && !Value_Range::supports_type_p (TREE_TYPE (m_op1)))) | |
172 | m_valid = false; | |
b40b3035 | 173 | return; |
51ce0638 | 174 | default: |
b40b3035 AM |
175 | gcc_unreachable (); |
176 | return; | |
51ce0638 | 177 | } |
b40b3035 AM |
178 | // If no range-op table entry handled this stmt, check for other supported |
179 | // statements. | |
180 | if (is_a <gcall *> (m_stmt)) | |
181 | maybe_builtin_call (); | |
03c6ba86 TC |
182 | else |
183 | maybe_non_standard (); | |
51ce0638 AM |
184 | } |
185 | ||
186 | // Calculate what we can determine of the range of this unary | |
187 | // statement's operand if the lhs of the expression has the range | |
188 | // LHS_RANGE. Return false if nothing can be determined. | |
189 | ||
190 | bool | |
191 | gimple_range_op_handler::calc_op1 (vrange &r, const vrange &lhs_range) | |
192 | { | |
193 | gcc_checking_assert (gimple_num_ops (m_stmt) < 3); | |
194 | // Give up on empty ranges. | |
195 | if (lhs_range.undefined_p ()) | |
196 | return false; | |
197 | ||
198 | // Unary operations require the type of the first operand in the | |
199 | // second range position. | |
200 | tree type = TREE_TYPE (operand1 ()); | |
201 | Value_Range type_range (type); | |
202 | type_range.set_varying (type); | |
203 | return op1_range (r, type, lhs_range, type_range); | |
204 | } | |
205 | ||
206 | // Calculate what we can determine of the range of this statement's | |
207 | // first operand if the lhs of the expression has the range LHS_RANGE | |
208 | // and the second operand has the range OP2_RANGE. Return false if | |
209 | // nothing can be determined. | |
210 | ||
211 | bool | |
212 | gimple_range_op_handler::calc_op1 (vrange &r, const vrange &lhs_range, | |
b565ac19 | 213 | const vrange &op2_range, relation_trio k) |
51ce0638 AM |
214 | { |
215 | // Give up on empty ranges. | |
216 | if (lhs_range.undefined_p ()) | |
217 | return false; | |
218 | ||
219 | // Unary operation are allowed to pass a range in for second operand | |
220 | // as there are often additional restrictions beyond the type which | |
221 | // can be imposed. See operator_cast::op1_range(). | |
222 | tree type = TREE_TYPE (operand1 ()); | |
223 | // If op2 is undefined, solve as if it is varying. | |
224 | if (op2_range.undefined_p ()) | |
225 | { | |
51ce0638 AM |
226 | if (gimple_num_ops (m_stmt) < 3) |
227 | return false; | |
a7a6649f AM |
228 | tree op2_type; |
229 | // This is sometimes invoked on single operand stmts. | |
230 | if (operand2 ()) | |
231 | op2_type = TREE_TYPE (operand2 ()); | |
232 | else | |
233 | op2_type = TREE_TYPE (operand1 ()); | |
51ce0638 AM |
234 | Value_Range trange (op2_type); |
235 | trange.set_varying (op2_type); | |
431cdfbe | 236 | return op1_range (r, type, lhs_range, trange, k); |
51ce0638 | 237 | } |
431cdfbe | 238 | return op1_range (r, type, lhs_range, op2_range, k); |
51ce0638 AM |
239 | } |
240 | ||
241 | // Calculate what we can determine of the range of this statement's | |
242 | // second operand if the lhs of the expression has the range LHS_RANGE | |
243 | // and the first operand has the range OP1_RANGE. Return false if | |
244 | // nothing can be determined. | |
245 | ||
246 | bool | |
247 | gimple_range_op_handler::calc_op2 (vrange &r, const vrange &lhs_range, | |
b565ac19 | 248 | const vrange &op1_range, relation_trio k) |
51ce0638 AM |
249 | { |
250 | // Give up on empty ranges. | |
251 | if (lhs_range.undefined_p ()) | |
252 | return false; | |
253 | ||
254 | tree type = TREE_TYPE (operand2 ()); | |
255 | // If op1 is undefined, solve as if it is varying. | |
256 | if (op1_range.undefined_p ()) | |
257 | { | |
258 | tree op1_type = TREE_TYPE (operand1 ()); | |
259 | Value_Range trange (op1_type); | |
260 | trange.set_varying (op1_type); | |
431cdfbe | 261 | return op2_range (r, type, lhs_range, trange, k); |
51ce0638 | 262 | } |
431cdfbe | 263 | return op2_range (r, type, lhs_range, op1_range, k); |
51ce0638 | 264 | } |
b40b3035 AM |
265 | |
266 | // -------------------------------------------------------------------- | |
267 | ||
268 | // Implement range operator for float CFN_BUILT_IN_CONSTANT_P. | |
269 | class cfn_constant_float_p : public range_operator_float | |
270 | { | |
271 | public: | |
272 | using range_operator_float::fold_range; | |
273 | virtual bool fold_range (irange &r, tree type, const frange &lh, | |
b565ac19 | 274 | const irange &, relation_trio) const |
b40b3035 AM |
275 | { |
276 | if (lh.singleton_p ()) | |
277 | { | |
278 | r.set (build_one_cst (type), build_one_cst (type)); | |
279 | return true; | |
280 | } | |
281 | if (cfun->after_inlining) | |
282 | { | |
283 | r.set_zero (type); | |
284 | return true; | |
285 | } | |
286 | return false; | |
287 | } | |
288 | } op_cfn_constant_float_p; | |
289 | ||
290 | // Implement range operator for integral CFN_BUILT_IN_CONSTANT_P. | |
291 | class cfn_constant_p : public range_operator | |
292 | { | |
293 | public: | |
294 | using range_operator::fold_range; | |
295 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
b565ac19 | 296 | const irange &, relation_trio) const |
b40b3035 AM |
297 | { |
298 | if (lh.singleton_p ()) | |
299 | { | |
300 | r.set (build_one_cst (type), build_one_cst (type)); | |
301 | return true; | |
302 | } | |
303 | if (cfun->after_inlining) | |
304 | { | |
305 | r.set_zero (type); | |
306 | return true; | |
307 | } | |
308 | return false; | |
309 | } | |
310 | } op_cfn_constant_p; | |
311 | ||
5f413dc4 RB |
312 | // Implement range operator for integral/pointer functions returning |
313 | // the first argument. | |
314 | class cfn_pass_through_arg1 : public range_operator | |
315 | { | |
316 | public: | |
317 | using range_operator::fold_range; | |
318 | virtual bool fold_range (irange &r, tree, const irange &lh, | |
319 | const irange &, relation_trio) const | |
320 | { | |
321 | r = lh; | |
322 | return true; | |
323 | } | |
324 | virtual bool op1_range (irange &r, tree, const irange &lhs, | |
325 | const irange &, relation_trio) const | |
326 | { | |
327 | r = lhs; | |
328 | return true; | |
329 | } | |
330 | } op_cfn_pass_through_arg1; | |
331 | ||
eb82b9f6 AM |
332 | // Implement range operator for CFN_BUILT_IN_SIGNBIT. |
333 | class cfn_signbit : public range_operator_float | |
334 | { | |
335 | public: | |
336 | using range_operator_float::fold_range; | |
98ad4527 | 337 | using range_operator_float::op1_range; |
eb82b9f6 | 338 | virtual bool fold_range (irange &r, tree type, const frange &lh, |
b565ac19 | 339 | const irange &, relation_trio) const override |
eb82b9f6 AM |
340 | { |
341 | bool signbit; | |
342 | if (lh.signbit_p (signbit)) | |
343 | { | |
344 | if (signbit) | |
345 | r.set_nonzero (type); | |
346 | else | |
347 | r.set_zero (type); | |
348 | return true; | |
349 | } | |
350 | return false; | |
351 | } | |
98ad4527 | 352 | virtual bool op1_range (frange &r, tree type, const irange &lhs, |
b565ac19 | 353 | const frange &, relation_trio) const override |
98ad4527 AH |
354 | { |
355 | if (lhs.zero_p ()) | |
356 | { | |
357 | r.set (type, dconst0, frange_val_max (type)); | |
358 | r.update_nan (false); | |
359 | return true; | |
360 | } | |
361 | if (!lhs.contains_p (build_zero_cst (lhs.type ()))) | |
362 | { | |
363 | REAL_VALUE_TYPE dconstm0 = dconst0; | |
364 | dconstm0.sign = 1; | |
365 | r.set (type, frange_val_min (type), dconstm0); | |
366 | r.update_nan (true); | |
367 | return true; | |
368 | } | |
369 | return false; | |
370 | } | |
eb82b9f6 AM |
371 | } op_cfn_signbit; |
372 | ||
8efc3834 AH |
373 | // Implement range operator for CFN_BUILT_IN_COPYSIGN |
374 | class cfn_copysign : public range_operator_float | |
375 | { | |
376 | public: | |
377 | using range_operator_float::fold_range; | |
378 | virtual bool fold_range (frange &r, tree type, const frange &lh, | |
b565ac19 | 379 | const frange &rh, relation_trio) const override |
8efc3834 AH |
380 | { |
381 | frange neg; | |
382 | range_op_handler abs_op (ABS_EXPR, type); | |
383 | range_op_handler neg_op (NEGATE_EXPR, type); | |
384 | if (!abs_op || !abs_op.fold_range (r, type, lh, frange (type))) | |
385 | return false; | |
386 | if (!neg_op || !neg_op.fold_range (neg, type, r, frange (type))) | |
387 | return false; | |
388 | ||
389 | bool signbit; | |
390 | if (rh.signbit_p (signbit)) | |
391 | { | |
392 | // If the sign is negative, flip the result from ABS, | |
393 | // otherwise leave things positive. | |
394 | if (signbit) | |
395 | r = neg; | |
396 | } | |
397 | else | |
398 | // If the sign is unknown, keep the positive and negative | |
399 | // alternatives. | |
400 | r.union_ (neg); | |
401 | return true; | |
402 | } | |
403 | } op_cfn_copysign; | |
404 | ||
2f5da730 AM |
405 | // Implement range operator for CFN_BUILT_IN_TOUPPER and CFN_BUILT_IN_TOLOWER. |
406 | class cfn_toupper_tolower : public range_operator | |
407 | { | |
408 | public: | |
409 | using range_operator::fold_range; | |
410 | cfn_toupper_tolower (bool toupper) { m_toupper = toupper; } | |
411 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
b565ac19 | 412 | const irange &, relation_trio) const; |
2f5da730 AM |
413 | private: |
414 | bool get_letter_range (tree type, irange &lowers, irange &uppers) const; | |
415 | bool m_toupper; | |
416 | } op_cfn_toupper (true), op_cfn_tolower (false); | |
417 | ||
418 | // Return TRUE if we recognize the target character set and return the | |
419 | // range for lower case and upper case letters. | |
420 | ||
421 | bool | |
422 | cfn_toupper_tolower::get_letter_range (tree type, irange &lowers, | |
423 | irange &uppers) const | |
424 | { | |
425 | // ASCII | |
426 | int a = lang_hooks.to_target_charset ('a'); | |
427 | int z = lang_hooks.to_target_charset ('z'); | |
428 | int A = lang_hooks.to_target_charset ('A'); | |
429 | int Z = lang_hooks.to_target_charset ('Z'); | |
430 | ||
431 | if ((z - a == 25) && (Z - A == 25)) | |
432 | { | |
433 | lowers = int_range<2> (build_int_cst (type, a), build_int_cst (type, z)); | |
434 | uppers = int_range<2> (build_int_cst (type, A), build_int_cst (type, Z)); | |
435 | return true; | |
436 | } | |
437 | // Unknown character set. | |
438 | return false; | |
439 | } | |
440 | ||
441 | bool | |
442 | cfn_toupper_tolower::fold_range (irange &r, tree type, const irange &lh, | |
b565ac19 | 443 | const irange &, relation_trio) const |
2f5da730 AM |
444 | { |
445 | int_range<3> lowers; | |
446 | int_range<3> uppers; | |
447 | if (!get_letter_range (type, lowers, uppers)) | |
448 | return false; | |
449 | ||
450 | r = lh; | |
451 | if (m_toupper) | |
452 | { | |
453 | // Return the range passed in without any lower case characters, | |
454 | // but including all the upper case ones. | |
455 | lowers.invert (); | |
456 | r.intersect (lowers); | |
457 | r.union_ (uppers); | |
458 | } | |
459 | else | |
460 | { | |
461 | // Return the range passed in without any lower case characters, | |
462 | // but including all the upper case ones. | |
463 | uppers.invert (); | |
464 | r.intersect (uppers); | |
465 | r.union_ (lowers); | |
466 | } | |
467 | return true; | |
468 | } | |
469 | ||
f50d1031 AH |
470 | // Implement range operator for CFN_BUILT_IN_FFS. |
471 | class cfn_ffs : public range_operator | |
5f730c65 AM |
472 | { |
473 | public: | |
474 | using range_operator::fold_range; | |
475 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
b565ac19 | 476 | const irange &, relation_trio) const |
5f730c65 AM |
477 | { |
478 | if (lh.undefined_p ()) | |
479 | return false; | |
480 | // __builtin_ffs* and __builtin_popcount* return [0, prec]. | |
481 | int prec = TYPE_PRECISION (lh.type ()); | |
482 | // If arg is non-zero, then ffs or popcount are non-zero. | |
483 | int mini = range_includes_zero_p (&lh) ? 0 : 1; | |
484 | int maxi = prec; | |
485 | ||
486 | // If some high bits are known to be zero, decrease the maximum. | |
487 | int_range_max tmp = lh; | |
488 | if (TYPE_SIGN (tmp.type ()) == SIGNED) | |
489 | range_cast (tmp, unsigned_type_for (tmp.type ())); | |
490 | wide_int max = tmp.upper_bound (); | |
491 | maxi = wi::floor_log2 (max) + 1; | |
492 | r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); | |
493 | return true; | |
494 | } | |
f50d1031 AH |
495 | } op_cfn_ffs; |
496 | ||
497 | // Implement range operator for CFN_BUILT_IN_POPCOUNT. | |
498 | class cfn_popcount : public cfn_ffs | |
499 | { | |
500 | public: | |
501 | using range_operator::fold_range; | |
502 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
b565ac19 | 503 | const irange &rh, relation_trio rel) const |
f50d1031 | 504 | { |
4c451631 AH |
505 | if (lh.undefined_p ()) |
506 | return false; | |
507 | unsigned prec = TYPE_PRECISION (type); | |
508 | wide_int nz = lh.get_nonzero_bits (); | |
509 | wide_int pop = wi::shwi (wi::popcount (nz), prec); | |
f50d1031 AH |
510 | // Calculating the popcount of a singleton is trivial. |
511 | if (lh.singleton_p ()) | |
512 | { | |
f50d1031 AH |
513 | r.set (type, pop, pop); |
514 | return true; | |
515 | } | |
4c451631 AH |
516 | if (cfn_ffs::fold_range (r, type, lh, rh, rel)) |
517 | { | |
518 | int_range<2> tmp (type, wi::zero (prec), pop); | |
519 | r.intersect (tmp); | |
520 | return true; | |
521 | } | |
522 | return false; | |
f50d1031 | 523 | } |
5f730c65 AM |
524 | } op_cfn_popcount; |
525 | ||
ae1669a9 AM |
526 | // Implement range operator for CFN_BUILT_IN_CLZ |
527 | class cfn_clz : public range_operator | |
528 | { | |
529 | public: | |
530 | cfn_clz (bool internal) { m_gimple_call_internal_p = internal; } | |
531 | using range_operator::fold_range; | |
532 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
b565ac19 | 533 | const irange &, relation_trio) const; |
ae1669a9 AM |
534 | private: |
535 | bool m_gimple_call_internal_p; | |
536 | } op_cfn_clz (false), op_cfn_clz_internal (true); | |
537 | ||
538 | bool | |
539 | cfn_clz::fold_range (irange &r, tree type, const irange &lh, | |
b565ac19 | 540 | const irange &, relation_trio) const |
ae1669a9 AM |
541 | { |
542 | // __builtin_c[lt]z* return [0, prec-1], except when the | |
543 | // argument is 0, but that is undefined behavior. | |
544 | // | |
545 | // For __builtin_c[lt]z* consider argument of 0 always undefined | |
546 | // behavior, for internal fns depending on C?Z_DEFINED_ALUE_AT_ZERO. | |
547 | if (lh.undefined_p ()) | |
548 | return false; | |
549 | int prec = TYPE_PRECISION (lh.type ()); | |
550 | int mini = 0; | |
551 | int maxi = prec - 1; | |
552 | int zerov = 0; | |
553 | scalar_int_mode mode = SCALAR_INT_TYPE_MODE (lh.type ()); | |
554 | if (m_gimple_call_internal_p) | |
555 | { | |
556 | if (optab_handler (clz_optab, mode) != CODE_FOR_nothing | |
557 | && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov) == 2) | |
558 | { | |
559 | // Only handle the single common value. | |
560 | if (zerov == prec) | |
561 | maxi = prec; | |
562 | else | |
563 | // Magic value to give up, unless we can prove arg is non-zero. | |
564 | mini = -2; | |
565 | } | |
566 | } | |
567 | ||
568 | // From clz of minimum we can compute result maximum. | |
569 | if (wi::gt_p (lh.lower_bound (), 0, TYPE_SIGN (lh.type ()))) | |
570 | { | |
571 | maxi = prec - 1 - wi::floor_log2 (lh.lower_bound ()); | |
572 | if (mini == -2) | |
573 | mini = 0; | |
574 | } | |
575 | else if (!range_includes_zero_p (&lh)) | |
576 | { | |
577 | mini = 0; | |
578 | maxi = prec - 1; | |
579 | } | |
580 | if (mini == -2) | |
581 | return false; | |
582 | // From clz of maximum we can compute result minimum. | |
583 | wide_int max = lh.upper_bound (); | |
584 | int newmini = prec - 1 - wi::floor_log2 (max); | |
585 | if (max == 0) | |
586 | { | |
587 | // If CLZ_DEFINED_VALUE_AT_ZERO is 2 with VALUE of prec, | |
588 | // return [prec, prec], otherwise ignore the range. | |
589 | if (maxi == prec) | |
590 | mini = prec; | |
591 | } | |
592 | else | |
593 | mini = newmini; | |
594 | ||
595 | if (mini == -2) | |
596 | return false; | |
597 | r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); | |
598 | return true; | |
599 | } | |
600 | ||
55738d8d AM |
601 | // Implement range operator for CFN_BUILT_IN_CTZ |
602 | class cfn_ctz : public range_operator | |
603 | { | |
604 | public: | |
605 | cfn_ctz (bool internal) { m_gimple_call_internal_p = internal; } | |
606 | using range_operator::fold_range; | |
607 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
b565ac19 | 608 | const irange &, relation_trio) const; |
55738d8d AM |
609 | private: |
610 | bool m_gimple_call_internal_p; | |
611 | } op_cfn_ctz (false), op_cfn_ctz_internal (true); | |
612 | ||
613 | bool | |
614 | cfn_ctz::fold_range (irange &r, tree type, const irange &lh, | |
b565ac19 | 615 | const irange &, relation_trio) const |
55738d8d AM |
616 | { |
617 | if (lh.undefined_p ()) | |
618 | return false; | |
619 | int prec = TYPE_PRECISION (lh.type ()); | |
620 | int mini = 0; | |
621 | int maxi = prec - 1; | |
622 | int zerov = 0; | |
623 | scalar_int_mode mode = SCALAR_INT_TYPE_MODE (lh.type ()); | |
624 | ||
625 | if (m_gimple_call_internal_p) | |
626 | { | |
627 | if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing | |
628 | && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov) == 2) | |
629 | { | |
630 | // Handle only the two common values. | |
631 | if (zerov == -1) | |
632 | mini = -1; | |
633 | else if (zerov == prec) | |
634 | maxi = prec; | |
635 | else | |
636 | // Magic value to give up, unless we can prove arg is non-zero. | |
637 | mini = -2; | |
638 | } | |
639 | } | |
640 | // If arg is non-zero, then use [0, prec - 1]. | |
641 | if (!range_includes_zero_p (&lh)) | |
642 | { | |
643 | mini = 0; | |
644 | maxi = prec - 1; | |
645 | } | |
646 | // If some high bits are known to be zero, we can decrease | |
647 | // the maximum. | |
648 | wide_int max = lh.upper_bound (); | |
649 | if (max == 0) | |
650 | { | |
651 | // Argument is [0, 0]. If CTZ_DEFINED_VALUE_AT_ZERO | |
652 | // is 2 with value -1 or prec, return [-1, -1] or [prec, prec]. | |
653 | // Otherwise ignore the range. | |
654 | if (mini == -1) | |
655 | maxi = -1; | |
656 | else if (maxi == prec) | |
657 | mini = prec; | |
658 | } | |
659 | // If value at zero is prec and 0 is in the range, we can't lower | |
660 | // the upper bound. We could create two separate ranges though, | |
661 | // [0,floor_log2(max)][prec,prec] though. | |
662 | else if (maxi != prec) | |
663 | maxi = wi::floor_log2 (max); | |
664 | ||
665 | if (mini == -2) | |
666 | return false; | |
667 | r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); | |
668 | return true; | |
669 | } | |
670 | ||
f7e62b09 AM |
671 | |
672 | // Implement range operator for CFN_BUILT_IN_ | |
673 | class cfn_clrsb : public range_operator | |
674 | { | |
675 | public: | |
676 | using range_operator::fold_range; | |
677 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
b565ac19 | 678 | const irange &, relation_trio) const |
f7e62b09 AM |
679 | { |
680 | if (lh.undefined_p ()) | |
681 | return false; | |
682 | int prec = TYPE_PRECISION (lh.type ()); | |
683 | r.set (build_int_cst (type, 0), build_int_cst (type, prec - 1)); | |
684 | return true; | |
685 | } | |
686 | } op_cfn_clrsb; | |
687 | ||
b6f670ff AM |
688 | |
689 | // Implement range operator for CFN_BUILT_IN_ | |
690 | class cfn_ubsan : public range_operator | |
691 | { | |
692 | public: | |
693 | cfn_ubsan (enum tree_code code) { m_code = code; } | |
694 | using range_operator::fold_range; | |
695 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
b565ac19 | 696 | const irange &rh, relation_trio rel) const |
b6f670ff AM |
697 | { |
698 | range_op_handler handler (m_code, type); | |
699 | gcc_checking_assert (handler); | |
700 | ||
701 | bool saved_flag_wrapv = flag_wrapv; | |
702 | // Pretend the arithmetic is wrapping. If there is any overflow, | |
703 | // we'll complain, but will actually do wrapping operation. | |
704 | flag_wrapv = 1; | |
705 | bool result = handler.fold_range (r, type, lh, rh, rel); | |
706 | flag_wrapv = saved_flag_wrapv; | |
707 | ||
708 | // If for both arguments vrp_valueize returned non-NULL, this should | |
709 | // have been already folded and if not, it wasn't folded because of | |
710 | // overflow. Avoid removing the UBSAN_CHECK_* calls in that case. | |
711 | if (result && r.singleton_p ()) | |
712 | r.set_varying (type); | |
713 | return result; | |
714 | } | |
715 | private: | |
716 | enum tree_code m_code; | |
717 | }; | |
718 | ||
719 | cfn_ubsan op_cfn_ubsan_add (PLUS_EXPR); | |
720 | cfn_ubsan op_cfn_ubsan_sub (MINUS_EXPR); | |
721 | cfn_ubsan op_cfn_ubsan_mul (MULT_EXPR); | |
722 | ||
c750e675 AM |
723 | |
724 | // Implement range operator for CFN_BUILT_IN_STRLEN | |
725 | class cfn_strlen : public range_operator | |
726 | { | |
727 | public: | |
728 | using range_operator::fold_range; | |
729 | virtual bool fold_range (irange &r, tree type, const irange &, | |
b565ac19 | 730 | const irange &, relation_trio) const |
c750e675 AM |
731 | { |
732 | tree max = vrp_val_max (ptrdiff_type_node); | |
733 | wide_int wmax | |
734 | = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); | |
735 | tree range_min = build_zero_cst (type); | |
736 | // To account for the terminating NULL, the maximum length | |
737 | // is one less than the maximum array size, which in turn | |
738 | // is one less than PTRDIFF_MAX (or SIZE_MAX where it's | |
739 | // smaller than the former type). | |
740 | // FIXME: Use max_object_size() - 1 here. | |
741 | tree range_max = wide_int_to_tree (type, wmax - 2); | |
742 | r.set (range_min, range_max); | |
743 | return true; | |
744 | } | |
745 | } op_cfn_strlen; | |
746 | ||
e7f035f6 AM |
747 | |
748 | // Implement range operator for CFN_BUILT_IN_GOACC_DIM | |
749 | class cfn_goacc_dim : public range_operator | |
750 | { | |
751 | public: | |
752 | cfn_goacc_dim (bool is_pos) { m_is_pos = is_pos; } | |
753 | using range_operator::fold_range; | |
754 | virtual bool fold_range (irange &r, tree type, const irange &lh, | |
b565ac19 | 755 | const irange &, relation_trio) const |
e7f035f6 AM |
756 | { |
757 | tree axis_tree; | |
758 | if (!lh.singleton_p (&axis_tree)) | |
759 | return false; | |
760 | HOST_WIDE_INT axis = TREE_INT_CST_LOW (axis_tree); | |
761 | int size = oacc_get_fn_dim_size (current_function_decl, axis); | |
762 | if (!size) | |
763 | // If it's dynamic, the backend might know a hardware limitation. | |
764 | size = targetm.goacc.dim_limit (axis); | |
765 | ||
766 | r.set (build_int_cst (type, m_is_pos ? 0 : 1), | |
767 | size | |
768 | ? build_int_cst (type, size - m_is_pos) : vrp_val_max (type)); | |
769 | return true; | |
770 | } | |
771 | private: | |
772 | bool m_is_pos; | |
773 | } op_cfn_goacc_dim_size (false), op_cfn_goacc_dim_pos (true); | |
774 | ||
5608e410 AM |
775 | |
776 | // Implement range operator for CFN_BUILT_IN_ | |
777 | class cfn_parity : public range_operator | |
778 | { | |
779 | public: | |
780 | using range_operator::fold_range; | |
781 | virtual bool fold_range (irange &r, tree type, const irange &, | |
b565ac19 | 782 | const irange &, relation_trio) const |
5608e410 AM |
783 | { |
784 | r.set (build_zero_cst (type), build_one_cst (type)); | |
785 | return true; | |
786 | } | |
787 | } op_cfn_parity; | |
788 | ||
03c6ba86 TC |
789 | // Set up a gimple_range_op_handler for any nonstandard function which can be |
790 | // supported via range-ops. | |
791 | ||
792 | void | |
793 | gimple_range_op_handler::maybe_non_standard () | |
794 | { | |
795 | range_operator *signed_op = ptr_op_widen_mult_signed; | |
796 | range_operator *unsigned_op = ptr_op_widen_mult_unsigned; | |
797 | if (gimple_code (m_stmt) == GIMPLE_ASSIGN) | |
798 | switch (gimple_assign_rhs_code (m_stmt)) | |
799 | { | |
800 | case WIDEN_PLUS_EXPR: | |
801 | { | |
802 | signed_op = ptr_op_widen_plus_signed; | |
803 | unsigned_op = ptr_op_widen_plus_unsigned; | |
804 | } | |
805 | gcc_fallthrough (); | |
806 | case WIDEN_MULT_EXPR: | |
807 | { | |
808 | m_valid = false; | |
809 | m_op1 = gimple_assign_rhs1 (m_stmt); | |
810 | m_op2 = gimple_assign_rhs2 (m_stmt); | |
811 | tree ret = gimple_assign_lhs (m_stmt); | |
812 | bool signed1 = TYPE_SIGN (TREE_TYPE (m_op1)) == SIGNED; | |
813 | bool signed2 = TYPE_SIGN (TREE_TYPE (m_op2)) == SIGNED; | |
814 | bool signed_ret = TYPE_SIGN (TREE_TYPE (ret)) == SIGNED; | |
815 | ||
816 | /* Normally these operands should all have the same sign, but | |
817 | some passes and violate this by taking mismatched sign args. At | |
818 | the moment the only one that's possible is mismatch inputs and | |
819 | unsigned output. Once ranger supports signs for the operands we | |
820 | can properly fix it, for now only accept the case we can do | |
821 | correctly. */ | |
822 | if ((signed1 ^ signed2) && signed_ret) | |
823 | return; | |
824 | ||
825 | m_valid = true; | |
826 | if (signed2 && !signed1) | |
827 | std::swap (m_op1, m_op2); | |
828 | ||
829 | if (signed1 || signed2) | |
830 | m_int = signed_op; | |
831 | else | |
832 | m_int = unsigned_op; | |
833 | break; | |
834 | } | |
835 | default: | |
836 | break; | |
837 | } | |
838 | } | |
839 | ||
b40b3035 AM |
840 | // Set up a gimple_range_op_handler for any built in function which can be |
841 | // supported via range-ops. | |
842 | ||
843 | void | |
844 | gimple_range_op_handler::maybe_builtin_call () | |
845 | { | |
846 | gcc_checking_assert (is_a <gcall *> (m_stmt)); | |
847 | ||
848 | gcall *call = as_a <gcall *> (m_stmt); | |
849 | combined_fn func = gimple_call_combined_fn (call); | |
850 | if (func == CFN_LAST) | |
851 | return; | |
852 | tree type = gimple_range_type (call); | |
853 | gcc_checking_assert (type); | |
854 | if (!Value_Range::supports_type_p (type)) | |
855 | return; | |
856 | ||
857 | switch (func) | |
858 | { | |
859 | case CFN_BUILT_IN_CONSTANT_P: | |
860 | m_op1 = gimple_call_arg (call, 0); | |
861 | m_valid = true; | |
862 | if (irange::supports_p (TREE_TYPE (m_op1))) | |
863 | m_int = &op_cfn_constant_p; | |
864 | else if (frange::supports_p (TREE_TYPE (m_op1))) | |
865 | m_float = &op_cfn_constant_float_p; | |
866 | else | |
867 | m_valid = false; | |
868 | break; | |
869 | ||
823e9097 | 870 | CASE_FLT_FN (CFN_BUILT_IN_SIGNBIT): |
eb82b9f6 AM |
871 | m_op1 = gimple_call_arg (call, 0); |
872 | m_float = &op_cfn_signbit; | |
873 | m_valid = true; | |
874 | break; | |
875 | ||
8efc3834 AH |
876 | CASE_CFN_COPYSIGN_ALL: |
877 | m_op1 = gimple_call_arg (call, 0); | |
878 | m_op2 = gimple_call_arg (call, 1); | |
879 | m_float = &op_cfn_copysign; | |
880 | m_valid = true; | |
881 | break; | |
882 | ||
2f5da730 AM |
883 | case CFN_BUILT_IN_TOUPPER: |
884 | case CFN_BUILT_IN_TOLOWER: | |
885 | // Only proceed If the argument is compatible with the LHS. | |
886 | m_op1 = gimple_call_arg (call, 0); | |
887 | if (range_compatible_p (type, TREE_TYPE (m_op1))) | |
888 | { | |
889 | m_valid = true; | |
890 | m_int = (func == CFN_BUILT_IN_TOLOWER) ? &op_cfn_tolower | |
891 | : &op_cfn_toupper; | |
892 | } | |
893 | break; | |
894 | ||
5f730c65 | 895 | CASE_CFN_FFS: |
f50d1031 AH |
896 | m_op1 = gimple_call_arg (call, 0); |
897 | m_int = &op_cfn_ffs; | |
898 | m_valid = true; | |
899 | break; | |
900 | ||
5f730c65 AM |
901 | CASE_CFN_POPCOUNT: |
902 | m_op1 = gimple_call_arg (call, 0); | |
903 | m_int = &op_cfn_popcount; | |
904 | m_valid = true; | |
905 | break; | |
906 | ||
ae1669a9 AM |
907 | CASE_CFN_CLZ: |
908 | m_op1 = gimple_call_arg (call, 0); | |
909 | m_valid = true; | |
910 | if (gimple_call_internal_p (call)) | |
911 | m_int = &op_cfn_clz_internal; | |
912 | else | |
913 | m_int = &op_cfn_clz; | |
914 | break; | |
915 | ||
55738d8d AM |
916 | CASE_CFN_CTZ: |
917 | m_op1 = gimple_call_arg (call, 0); | |
918 | m_valid = true; | |
919 | if (gimple_call_internal_p (call)) | |
920 | m_int = &op_cfn_ctz_internal; | |
921 | else | |
922 | m_int = &op_cfn_ctz; | |
923 | break; | |
924 | ||
f7e62b09 AM |
925 | CASE_CFN_CLRSB: |
926 | m_op1 = gimple_call_arg (call, 0); | |
927 | m_valid = true; | |
928 | m_int = &op_cfn_clrsb; | |
929 | break; | |
930 | ||
b6f670ff AM |
931 | case CFN_UBSAN_CHECK_ADD: |
932 | m_op1 = gimple_call_arg (call, 0); | |
933 | m_op2 = gimple_call_arg (call, 1); | |
934 | m_valid = true; | |
935 | m_int = &op_cfn_ubsan_add; | |
936 | break; | |
937 | ||
938 | case CFN_UBSAN_CHECK_SUB: | |
939 | m_op1 = gimple_call_arg (call, 0); | |
940 | m_op2 = gimple_call_arg (call, 1); | |
941 | m_valid = true; | |
942 | m_int = &op_cfn_ubsan_sub; | |
943 | break; | |
944 | ||
945 | case CFN_UBSAN_CHECK_MUL: | |
946 | m_op1 = gimple_call_arg (call, 0); | |
947 | m_op2 = gimple_call_arg (call, 1); | |
948 | m_valid = true; | |
949 | m_int = &op_cfn_ubsan_mul; | |
950 | break; | |
951 | ||
c750e675 AM |
952 | case CFN_BUILT_IN_STRLEN: |
953 | { | |
954 | tree lhs = gimple_call_lhs (call); | |
955 | if (lhs && ptrdiff_type_node && (TYPE_PRECISION (ptrdiff_type_node) | |
956 | == TYPE_PRECISION (TREE_TYPE (lhs)))) | |
957 | { | |
958 | m_op1 = gimple_call_arg (call, 0); | |
959 | m_valid = true; | |
960 | m_int = &op_cfn_strlen; | |
961 | } | |
962 | break; | |
963 | } | |
964 | ||
e7f035f6 AM |
965 | // Optimizing these two internal functions helps the loop |
966 | // optimizer eliminate outer comparisons. Size is [1,N] | |
967 | // and pos is [0,N-1]. | |
968 | case CFN_GOACC_DIM_SIZE: | |
969 | // This call will ensure all the asserts are triggered. | |
970 | oacc_get_ifn_dim_arg (call); | |
971 | m_op1 = gimple_call_arg (call, 0); | |
972 | m_valid = true; | |
973 | m_int = &op_cfn_goacc_dim_size; | |
974 | break; | |
975 | ||
976 | case CFN_GOACC_DIM_POS: | |
977 | // This call will ensure all the asserts are triggered. | |
978 | oacc_get_ifn_dim_arg (call); | |
979 | m_op1 = gimple_call_arg (call, 0); | |
980 | m_valid = true; | |
981 | m_int = &op_cfn_goacc_dim_pos; | |
982 | break; | |
983 | ||
5608e410 AM |
984 | CASE_CFN_PARITY: |
985 | m_valid = true; | |
986 | m_int = &op_cfn_parity; | |
987 | break; | |
988 | ||
5f413dc4 RB |
989 | case CFN_BUILT_IN_EXPECT: |
990 | case CFN_BUILT_IN_EXPECT_WITH_PROBABILITY: | |
991 | m_valid = true; | |
992 | m_op1 = gimple_call_arg (call, 0); | |
993 | m_int = &op_cfn_pass_through_arg1; | |
994 | break; | |
995 | ||
b40b3035 AM |
996 | default: |
997 | break; | |
998 | } | |
999 | } |