]>
Commit | Line | Data |
---|---|---|
4c85ff75 AM |
1 | /* Code for GIMPLE range related routines. |
2 | Copyright (C) 2019-2021 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-fold.h" | |
33 | #include "wide-int.h" | |
34 | #include "fold-const.h" | |
35 | #include "case-cfn-macros.h" | |
36 | #include "omp-general.h" | |
37 | #include "cfgloop.h" | |
38 | #include "tree-ssa-loop.h" | |
39 | #include "tree-scalar-evolution.h" | |
d5a8c138 | 40 | #include "langhooks.h" |
4c85ff75 AM |
41 | #include "vr-values.h" |
42 | #include "range.h" | |
43 | #include "value-query.h" | |
44 | #include "range-op.h" | |
e68c8280 | 45 | #include "gimple-range.h" |
4c85ff75 AM |
46 | // Construct a fur_source, and set the m_query field. |
47 | ||
48 | fur_source::fur_source (range_query *q) | |
49 | { | |
50 | if (q) | |
51 | m_query = q; | |
52 | else if (cfun) | |
53 | m_query = get_range_query (cfun); | |
54 | else | |
55 | m_query = get_global_range_query (); | |
56 | m_gori = NULL; | |
57 | } | |
58 | ||
59 | // Invoke range_of_expr on EXPR. | |
60 | ||
61 | bool | |
62 | fur_source::get_operand (irange &r, tree expr) | |
63 | { | |
64 | return m_query->range_of_expr (r, expr); | |
65 | } | |
66 | ||
67 | // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current | |
68 | // range_query to get the range on the edge. | |
69 | ||
70 | bool | |
71 | fur_source::get_phi_operand (irange &r, tree expr, edge e) | |
72 | { | |
73 | return m_query->range_on_edge (r, e, expr); | |
74 | } | |
75 | ||
76 | // Default is no relation. | |
77 | ||
78 | relation_kind | |
79 | fur_source::query_relation (tree op1 ATTRIBUTE_UNUSED, | |
80 | tree op2 ATTRIBUTE_UNUSED) | |
81 | { | |
82 | return VREL_NONE; | |
83 | } | |
84 | ||
85 | // Default registers nothing. | |
86 | ||
87 | void | |
88 | fur_source::register_relation (gimple *s ATTRIBUTE_UNUSED, | |
89 | relation_kind k ATTRIBUTE_UNUSED, | |
90 | tree op1 ATTRIBUTE_UNUSED, | |
91 | tree op2 ATTRIBUTE_UNUSED) | |
92 | { | |
93 | } | |
94 | ||
95 | // Default registers nothing. | |
96 | ||
97 | void | |
98 | fur_source::register_relation (edge e ATTRIBUTE_UNUSED, | |
99 | relation_kind k ATTRIBUTE_UNUSED, | |
100 | tree op1 ATTRIBUTE_UNUSED, | |
101 | tree op2 ATTRIBUTE_UNUSED) | |
102 | { | |
103 | } | |
104 | ||
105 | // This version of fur_source will pick a range up off an edge. | |
106 | ||
107 | class fur_edge : public fur_source | |
108 | { | |
109 | public: | |
110 | fur_edge (edge e, range_query *q = NULL); | |
111 | virtual bool get_operand (irange &r, tree expr) OVERRIDE; | |
112 | virtual bool get_phi_operand (irange &r, tree expr, edge e) OVERRIDE; | |
113 | private: | |
114 | edge m_edge; | |
115 | }; | |
116 | ||
117 | // Instantiate an edge based fur_source. | |
118 | ||
119 | inline | |
120 | fur_edge::fur_edge (edge e, range_query *q) : fur_source (q) | |
121 | { | |
122 | m_edge = e; | |
123 | } | |
124 | ||
125 | // Get the value of EXPR on edge m_edge. | |
126 | ||
127 | bool | |
128 | fur_edge::get_operand (irange &r, tree expr) | |
129 | { | |
130 | return m_query->range_on_edge (r, m_edge, expr); | |
131 | } | |
132 | ||
133 | // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current | |
134 | // range_query to get the range on the edge. | |
135 | ||
136 | bool | |
137 | fur_edge::get_phi_operand (irange &r, tree expr, edge e) | |
138 | { | |
139 | // Edge to edge recalculations not supoprted yet, until we sort it out. | |
140 | gcc_checking_assert (e == m_edge); | |
141 | return m_query->range_on_edge (r, e, expr); | |
142 | } | |
143 | ||
144 | // Instantiate a stmt based fur_source. | |
145 | ||
146 | fur_stmt::fur_stmt (gimple *s, range_query *q) : fur_source (q) | |
147 | { | |
148 | m_stmt = s; | |
149 | } | |
150 | ||
151 | // Retreive range of EXPR as it occurs as a use on stmt M_STMT. | |
152 | ||
153 | bool | |
154 | fur_stmt::get_operand (irange &r, tree expr) | |
155 | { | |
156 | return m_query->range_of_expr (r, expr, m_stmt); | |
157 | } | |
158 | ||
159 | // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current | |
160 | // range_query to get the range on the edge. | |
161 | ||
162 | bool | |
163 | fur_stmt::get_phi_operand (irange &r, tree expr, edge e) | |
164 | { | |
165 | // Pick up the range of expr from edge E. | |
166 | fur_edge e_src (e, m_query); | |
167 | return e_src.get_operand (r, expr); | |
168 | } | |
169 | ||
170 | // Return relation based from m_stmt. | |
171 | ||
172 | relation_kind | |
173 | fur_stmt::query_relation (tree op1, tree op2) | |
174 | { | |
175 | return m_query->query_relation (m_stmt, op1, op2); | |
176 | } | |
177 | ||
178 | // Instantiate a stmt based fur_source with a GORI object. | |
179 | ||
180 | ||
181 | fur_depend::fur_depend (gimple *s, gori_compute *gori, range_query *q) | |
182 | : fur_stmt (s, q) | |
183 | { | |
184 | gcc_checking_assert (gori); | |
185 | m_gori = gori; | |
186 | // Set relations if there is an oracle in the range_query. | |
187 | // This will enable registering of relationships as they are discovered. | |
188 | m_oracle = q->oracle (); | |
189 | ||
190 | } | |
191 | ||
192 | // Register a relation on a stmt if there is an oracle. | |
193 | ||
194 | void | |
195 | fur_depend::register_relation (gimple *s, relation_kind k, tree op1, tree op2) | |
196 | { | |
197 | if (m_oracle) | |
3674d8e6 | 198 | m_oracle->register_stmt (s, k, op1, op2); |
4c85ff75 AM |
199 | } |
200 | ||
201 | // Register a relation on an edge if there is an oracle. | |
202 | ||
203 | void | |
204 | fur_depend::register_relation (edge e, relation_kind k, tree op1, tree op2) | |
205 | { | |
206 | if (m_oracle) | |
3674d8e6 | 207 | m_oracle->register_edge (e, k, op1, op2); |
4c85ff75 AM |
208 | } |
209 | ||
210 | // This version of fur_source will pick a range up from a list of ranges | |
211 | // supplied by the caller. | |
212 | ||
213 | class fur_list : public fur_source | |
214 | { | |
215 | public: | |
216 | fur_list (irange &r1); | |
217 | fur_list (irange &r1, irange &r2); | |
218 | fur_list (unsigned num, irange *list); | |
219 | virtual bool get_operand (irange &r, tree expr) OVERRIDE; | |
220 | virtual bool get_phi_operand (irange &r, tree expr, edge e) OVERRIDE; | |
221 | private: | |
222 | int_range_max m_local[2]; | |
223 | irange *m_list; | |
224 | unsigned m_index; | |
225 | unsigned m_limit; | |
226 | }; | |
227 | ||
228 | // One range supplied for unary operations. | |
229 | ||
230 | fur_list::fur_list (irange &r1) : fur_source (NULL) | |
231 | { | |
232 | m_list = m_local; | |
233 | m_index = 0; | |
234 | m_limit = 1; | |
235 | m_local[0] = r1; | |
236 | } | |
237 | ||
238 | // Two ranges supplied for binary operations. | |
239 | ||
240 | fur_list::fur_list (irange &r1, irange &r2) : fur_source (NULL) | |
241 | { | |
242 | m_list = m_local; | |
243 | m_index = 0; | |
244 | m_limit = 2; | |
245 | m_local[0] = r1; | |
246 | m_local[0] = r2; | |
247 | } | |
248 | ||
249 | // Arbitrary number of ranges in a vector. | |
250 | ||
251 | fur_list::fur_list (unsigned num, irange *list) : fur_source (NULL) | |
252 | { | |
253 | m_list = list; | |
254 | m_index = 0; | |
255 | m_limit = num; | |
256 | } | |
257 | ||
258 | // Get the next operand from the vector, ensure types are compatible. | |
259 | ||
260 | bool | |
261 | fur_list::get_operand (irange &r, tree expr) | |
262 | { | |
263 | if (m_index >= m_limit) | |
264 | return m_query->range_of_expr (r, expr); | |
265 | r = m_list[m_index++]; | |
266 | gcc_checking_assert (range_compatible_p (TREE_TYPE (expr), r.type ())); | |
267 | return true; | |
268 | } | |
269 | ||
270 | // This will simply pick the next operand from the vector. | |
271 | bool | |
272 | fur_list::get_phi_operand (irange &r, tree expr, edge e ATTRIBUTE_UNUSED) | |
273 | { | |
274 | return get_operand (r, expr); | |
275 | } | |
276 | ||
277 | // Fold stmt S into range R using R1 as the first operand. | |
278 | ||
279 | bool | |
280 | fold_range (irange &r, gimple *s, irange &r1) | |
281 | { | |
282 | fold_using_range f; | |
283 | fur_list src (r1); | |
284 | return f.fold_stmt (r, s, src); | |
285 | } | |
286 | ||
287 | // Fold stmt S into range R using R1 and R2 as the first two operands. | |
288 | ||
289 | bool | |
290 | fold_range (irange &r, gimple *s, irange &r1, irange &r2) | |
291 | { | |
292 | fold_using_range f; | |
293 | fur_list src (r1, r2); | |
294 | return f.fold_stmt (r, s, src); | |
295 | } | |
296 | ||
297 | // Fold stmt S into range R using NUM_ELEMENTS from VECTOR as the initial | |
298 | // operands encountered. | |
299 | ||
300 | bool | |
301 | fold_range (irange &r, gimple *s, unsigned num_elements, irange *vector) | |
302 | { | |
303 | fold_using_range f; | |
304 | fur_list src (num_elements, vector); | |
305 | return f.fold_stmt (r, s, src); | |
306 | } | |
307 | ||
308 | // Fold stmt S into range R using range query Q. | |
309 | ||
310 | bool | |
311 | fold_range (irange &r, gimple *s, range_query *q) | |
312 | { | |
313 | fold_using_range f; | |
314 | fur_stmt src (s, q); | |
315 | return f.fold_stmt (r, s, src); | |
316 | } | |
317 | ||
318 | // Recalculate stmt S into R using range query Q as if it were on edge ON_EDGE. | |
319 | ||
320 | bool | |
321 | fold_range (irange &r, gimple *s, edge on_edge, range_query *q) | |
322 | { | |
323 | fold_using_range f; | |
324 | fur_edge src (on_edge, q); | |
325 | return f.fold_stmt (r, s, src); | |
326 | } | |
327 | ||
328 | // ------------------------------------------------------------------------- | |
329 | ||
330 | // Adjust the range for a pointer difference where the operands came | |
331 | // from a memchr. | |
332 | // | |
333 | // This notices the following sequence: | |
334 | // | |
335 | // def = __builtin_memchr (arg, 0, sz) | |
336 | // n = def - arg | |
337 | // | |
338 | // The range for N can be narrowed to [0, PTRDIFF_MAX - 1]. | |
339 | ||
340 | static void | |
341 | adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt) | |
342 | { | |
343 | tree op0 = gimple_assign_rhs1 (diff_stmt); | |
344 | tree op1 = gimple_assign_rhs2 (diff_stmt); | |
345 | tree op0_ptype = TREE_TYPE (TREE_TYPE (op0)); | |
346 | tree op1_ptype = TREE_TYPE (TREE_TYPE (op1)); | |
347 | gimple *call; | |
348 | ||
349 | if (TREE_CODE (op0) == SSA_NAME | |
350 | && TREE_CODE (op1) == SSA_NAME | |
351 | && (call = SSA_NAME_DEF_STMT (op0)) | |
352 | && is_gimple_call (call) | |
353 | && gimple_call_builtin_p (call, BUILT_IN_MEMCHR) | |
354 | && TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node) | |
355 | && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node) | |
356 | && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node) | |
357 | && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node) | |
358 | && gimple_call_builtin_p (call, BUILT_IN_MEMCHR) | |
359 | && vrp_operand_equal_p (op1, gimple_call_arg (call, 0)) | |
360 | && integer_zerop (gimple_call_arg (call, 1))) | |
361 | { | |
362 | tree max = vrp_val_max (ptrdiff_type_node); | |
ad451b02 AM |
363 | unsigned prec = TYPE_PRECISION (TREE_TYPE (max)); |
364 | wide_int wmaxm1 = wi::to_wide (max, prec) - 1; | |
365 | res.intersect (wi::zero (prec), wmaxm1); | |
4c85ff75 AM |
366 | } |
367 | } | |
368 | ||
bccf4b88 AH |
369 | // Adjust the range for an IMAGPART_EXPR. |
370 | ||
371 | static void | |
372 | adjust_imagpart_expr (irange &res, const gimple *stmt) | |
373 | { | |
374 | tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); | |
375 | ||
376 | if (TREE_CODE (name) != SSA_NAME || !SSA_NAME_DEF_STMT (name)) | |
377 | return; | |
378 | ||
379 | gimple *def_stmt = SSA_NAME_DEF_STMT (name); | |
380 | if (is_gimple_call (def_stmt) && gimple_call_internal_p (def_stmt)) | |
381 | { | |
382 | switch (gimple_call_internal_fn (def_stmt)) | |
383 | { | |
384 | case IFN_ADD_OVERFLOW: | |
385 | case IFN_SUB_OVERFLOW: | |
386 | case IFN_MUL_OVERFLOW: | |
387 | case IFN_ATOMIC_COMPARE_EXCHANGE: | |
388 | { | |
389 | int_range<2> r; | |
390 | r.set_varying (boolean_type_node); | |
391 | tree type = TREE_TYPE (gimple_assign_lhs (stmt)); | |
392 | range_cast (r, type); | |
393 | res.intersect (r); | |
394 | } | |
395 | default: | |
396 | break; | |
397 | } | |
398 | return; | |
399 | } | |
400 | if (is_gimple_assign (def_stmt)) | |
401 | { | |
402 | tree cst = gimple_assign_rhs1 (def_stmt); | |
403 | if (TREE_CODE (cst) == COMPLEX_CST) | |
404 | { | |
ad451b02 AM |
405 | wide_int imag = wi::to_wide (TREE_IMAGPART (cst)); |
406 | res.intersect (imag, imag); | |
bccf4b88 AH |
407 | } |
408 | } | |
409 | } | |
410 | ||
411 | // Adjust the range for a REALPART_EXPR. | |
412 | ||
413 | static void | |
414 | adjust_realpart_expr (irange &res, const gimple *stmt) | |
415 | { | |
416 | tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); | |
417 | ||
418 | if (TREE_CODE (name) != SSA_NAME) | |
419 | return; | |
420 | ||
421 | gimple *def_stmt = SSA_NAME_DEF_STMT (name); | |
422 | if (!SSA_NAME_DEF_STMT (name)) | |
423 | return; | |
424 | ||
425 | if (is_gimple_assign (def_stmt)) | |
426 | { | |
427 | tree cst = gimple_assign_rhs1 (def_stmt); | |
428 | if (TREE_CODE (cst) == COMPLEX_CST) | |
429 | { | |
430 | tree imag = TREE_REALPART (cst); | |
431 | int_range<2> tmp (imag, imag); | |
432 | res.intersect (tmp); | |
433 | } | |
434 | } | |
435 | } | |
436 | ||
4c85ff75 AM |
437 | // This function looks for situations when walking the use/def chains |
438 | // may provide additonal contextual range information not exposed on | |
bccf4b88 | 439 | // this statement. |
4c85ff75 AM |
440 | |
441 | static void | |
442 | gimple_range_adjustment (irange &res, const gimple *stmt) | |
443 | { | |
444 | switch (gimple_expr_code (stmt)) | |
445 | { | |
446 | case POINTER_DIFF_EXPR: | |
447 | adjust_pointer_diff_expr (res, stmt); | |
448 | return; | |
449 | ||
450 | case IMAGPART_EXPR: | |
bccf4b88 AH |
451 | adjust_imagpart_expr (res, stmt); |
452 | return; | |
453 | ||
454 | case REALPART_EXPR: | |
455 | adjust_realpart_expr (res, stmt); | |
456 | return; | |
4c85ff75 AM |
457 | |
458 | default: | |
459 | break; | |
460 | } | |
461 | } | |
462 | ||
463 | // Return the base of the RHS of an assignment. | |
464 | ||
465 | static tree | |
466 | gimple_range_base_of_assignment (const gimple *stmt) | |
467 | { | |
468 | gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN); | |
469 | tree op1 = gimple_assign_rhs1 (stmt); | |
470 | if (gimple_assign_rhs_code (stmt) == ADDR_EXPR) | |
471 | return get_base_address (TREE_OPERAND (op1, 0)); | |
472 | return op1; | |
473 | } | |
474 | ||
475 | // Return the first operand of this statement if it is a valid operand | |
476 | // supported by ranges, otherwise return NULL_TREE. Special case is | |
477 | // &(SSA_NAME expr), return the SSA_NAME instead of the ADDR expr. | |
478 | ||
479 | tree | |
480 | gimple_range_operand1 (const gimple *stmt) | |
481 | { | |
482 | gcc_checking_assert (gimple_range_handler (stmt)); | |
483 | ||
484 | switch (gimple_code (stmt)) | |
485 | { | |
486 | case GIMPLE_COND: | |
487 | return gimple_cond_lhs (stmt); | |
488 | case GIMPLE_ASSIGN: | |
489 | { | |
490 | tree base = gimple_range_base_of_assignment (stmt); | |
491 | if (base && TREE_CODE (base) == MEM_REF) | |
492 | { | |
493 | // If the base address is an SSA_NAME, we return it | |
494 | // here. This allows processing of the range of that | |
495 | // name, while the rest of the expression is simply | |
496 | // ignored. The code in range_ops will see the | |
497 | // ADDR_EXPR and do the right thing. | |
498 | tree ssa = TREE_OPERAND (base, 0); | |
499 | if (TREE_CODE (ssa) == SSA_NAME) | |
500 | return ssa; | |
501 | } | |
502 | return base; | |
503 | } | |
504 | default: | |
505 | break; | |
506 | } | |
507 | return NULL; | |
508 | } | |
509 | ||
510 | // Return the second operand of statement STMT, otherwise return NULL_TREE. | |
511 | ||
512 | tree | |
513 | gimple_range_operand2 (const gimple *stmt) | |
514 | { | |
515 | gcc_checking_assert (gimple_range_handler (stmt)); | |
516 | ||
517 | switch (gimple_code (stmt)) | |
518 | { | |
519 | case GIMPLE_COND: | |
520 | return gimple_cond_rhs (stmt); | |
521 | case GIMPLE_ASSIGN: | |
522 | if (gimple_num_ops (stmt) >= 3) | |
523 | return gimple_assign_rhs2 (stmt); | |
524 | default: | |
525 | break; | |
526 | } | |
527 | return NULL_TREE; | |
528 | } | |
529 | ||
530 | // Calculate a range for statement S and return it in R. If NAME is provided it | |
531 | // represents the SSA_NAME on the LHS of the statement. It is only required | |
532 | // if there is more than one lhs/output. If a range cannot | |
533 | // be calculated, return false. | |
534 | ||
535 | bool | |
536 | fold_using_range::fold_stmt (irange &r, gimple *s, fur_source &src, tree name) | |
537 | { | |
538 | bool res = false; | |
539 | // If name and S are specified, make sure it is an LHS of S. | |
540 | gcc_checking_assert (!name || !gimple_get_lhs (s) || | |
541 | name == gimple_get_lhs (s)); | |
542 | ||
543 | if (!name) | |
544 | name = gimple_get_lhs (s); | |
545 | ||
546 | // Process addresses. | |
547 | if (gimple_code (s) == GIMPLE_ASSIGN | |
548 | && gimple_assign_rhs_code (s) == ADDR_EXPR) | |
549 | return range_of_address (r, s, src); | |
550 | ||
551 | if (gimple_range_handler (s)) | |
552 | res = range_of_range_op (r, s, src); | |
553 | else if (is_a<gphi *>(s)) | |
554 | res = range_of_phi (r, as_a<gphi *> (s), src); | |
555 | else if (is_a<gcall *>(s)) | |
556 | res = range_of_call (r, as_a<gcall *> (s), src); | |
557 | else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR) | |
558 | res = range_of_cond_expr (r, as_a<gassign *> (s), src); | |
559 | ||
560 | if (!res) | |
561 | { | |
478cc962 AM |
562 | // If no name specified or range is unsupported, bail. |
563 | if (!name || !gimple_range_ssa_p (name)) | |
4c85ff75 AM |
564 | return false; |
565 | // We don't understand the stmt, so return the global range. | |
566 | r = gimple_range_global (name); | |
567 | return true; | |
568 | } | |
569 | ||
570 | if (r.undefined_p ()) | |
571 | return true; | |
572 | ||
573 | // We sometimes get compatible types copied from operands, make sure | |
574 | // the correct type is being returned. | |
575 | if (name && TREE_TYPE (name) != r.type ()) | |
576 | { | |
577 | gcc_checking_assert (range_compatible_p (r.type (), TREE_TYPE (name))); | |
578 | range_cast (r, TREE_TYPE (name)); | |
579 | } | |
580 | return true; | |
581 | } | |
582 | ||
583 | // Calculate a range for range_op statement S and return it in R. If any | |
584 | // If a range cannot be calculated, return false. | |
585 | ||
586 | bool | |
587 | fold_using_range::range_of_range_op (irange &r, gimple *s, fur_source &src) | |
588 | { | |
589 | int_range_max range1, range2; | |
478cc962 AM |
590 | tree type = gimple_range_type (s); |
591 | if (!type) | |
592 | return false; | |
4c85ff75 AM |
593 | range_operator *handler = gimple_range_handler (s); |
594 | gcc_checking_assert (handler); | |
4c85ff75 AM |
595 | |
596 | tree lhs = gimple_get_lhs (s); | |
597 | tree op1 = gimple_range_operand1 (s); | |
598 | tree op2 = gimple_range_operand2 (s); | |
599 | ||
600 | if (src.get_operand (range1, op1)) | |
601 | { | |
602 | if (!op2) | |
603 | { | |
604 | // Fold range, and register any dependency if available. | |
605 | int_range<2> r2 (type); | |
606 | handler->fold_range (r, type, range1, r2); | |
607 | if (lhs && gimple_range_ssa_p (op1)) | |
608 | { | |
609 | if (src.gori ()) | |
610 | src.gori ()->register_dependency (lhs, op1); | |
611 | relation_kind rel; | |
612 | rel = handler->lhs_op1_relation (r, range1, range1); | |
613 | if (rel != VREL_NONE) | |
614 | src.register_relation (s, rel, lhs, op1); | |
615 | } | |
616 | } | |
617 | else if (src.get_operand (range2, op2)) | |
618 | { | |
619 | relation_kind rel = src.query_relation (op1, op2); | |
620 | if (dump_file && (dump_flags & TDF_DETAILS) && rel != VREL_NONE) | |
621 | { | |
622 | fprintf (dump_file, " folding with relation "); | |
2f0b6a97 | 623 | print_generic_expr (dump_file, op1, TDF_SLIM); |
4c85ff75 | 624 | print_relation (dump_file, rel); |
2f0b6a97 | 625 | print_generic_expr (dump_file, op2, TDF_SLIM); |
4c85ff75 AM |
626 | fputc ('\n', dump_file); |
627 | } | |
628 | // Fold range, and register any dependency if available. | |
629 | handler->fold_range (r, type, range1, range2, rel); | |
630 | relation_fold_and_or (r, s, src); | |
631 | if (lhs) | |
632 | { | |
633 | if (src.gori ()) | |
634 | { | |
635 | src.gori ()->register_dependency (lhs, op1); | |
636 | src.gori ()->register_dependency (lhs, op2); | |
637 | } | |
638 | if (gimple_range_ssa_p (op1)) | |
639 | { | |
640 | rel = handler->lhs_op1_relation (r, range1, range2); | |
641 | if (rel != VREL_NONE) | |
642 | src.register_relation (s, rel, lhs, op1); | |
643 | } | |
644 | if (gimple_range_ssa_p (op2)) | |
645 | { | |
646 | rel= handler->lhs_op2_relation (r, range1, range2); | |
647 | if (rel != VREL_NONE) | |
648 | src.register_relation (s, rel, lhs, op2); | |
649 | } | |
650 | } | |
fec75ab8 AH |
651 | // Check for an existing BB, as we maybe asked to fold an |
652 | // artificial statement not in the CFG. | |
653 | else if (is_a<gcond *> (s) && gimple_bb (s)) | |
198bc5ec AH |
654 | { |
655 | basic_block bb = gimple_bb (s); | |
656 | edge e0 = EDGE_SUCC (bb, 0); | |
657 | edge e1 = EDGE_SUCC (bb, 1); | |
658 | ||
659 | if (!single_pred_p (e0->dest)) | |
660 | e0 = NULL; | |
661 | if (!single_pred_p (e1->dest)) | |
662 | e1 = NULL; | |
663 | src.register_outgoing_edges (as_a<gcond *> (s), r, e0, e1); | |
664 | } | |
4c85ff75 AM |
665 | } |
666 | else | |
667 | r.set_varying (type); | |
668 | } | |
669 | else | |
670 | r.set_varying (type); | |
671 | // Make certain range-op adjustments that aren't handled any other way. | |
672 | gimple_range_adjustment (r, s); | |
673 | return true; | |
674 | } | |
675 | ||
676 | // Calculate the range of an assignment containing an ADDR_EXPR. | |
677 | // Return the range in R. | |
678 | // If a range cannot be calculated, set it to VARYING and return true. | |
679 | ||
680 | bool | |
681 | fold_using_range::range_of_address (irange &r, gimple *stmt, fur_source &src) | |
682 | { | |
683 | gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN); | |
684 | gcc_checking_assert (gimple_assign_rhs_code (stmt) == ADDR_EXPR); | |
685 | ||
686 | bool strict_overflow_p; | |
687 | tree expr = gimple_assign_rhs1 (stmt); | |
688 | poly_int64 bitsize, bitpos; | |
689 | tree offset; | |
690 | machine_mode mode; | |
691 | int unsignedp, reversep, volatilep; | |
692 | tree base = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, | |
693 | &bitpos, &offset, &mode, &unsignedp, | |
694 | &reversep, &volatilep); | |
695 | ||
696 | ||
697 | if (base != NULL_TREE | |
698 | && TREE_CODE (base) == MEM_REF | |
699 | && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) | |
700 | { | |
701 | tree ssa = TREE_OPERAND (base, 0); | |
702 | tree lhs = gimple_get_lhs (stmt); | |
703 | if (lhs && gimple_range_ssa_p (ssa) && src.gori ()) | |
704 | src.gori ()->register_dependency (lhs, ssa); | |
705 | gcc_checking_assert (irange::supports_type_p (TREE_TYPE (ssa))); | |
706 | src.get_operand (r, ssa); | |
707 | range_cast (r, TREE_TYPE (gimple_assign_rhs1 (stmt))); | |
708 | ||
709 | poly_offset_int off = 0; | |
710 | bool off_cst = false; | |
711 | if (offset == NULL_TREE || TREE_CODE (offset) == INTEGER_CST) | |
712 | { | |
713 | off = mem_ref_offset (base); | |
714 | if (offset) | |
715 | off += poly_offset_int::from (wi::to_poly_wide (offset), | |
716 | SIGNED); | |
717 | off <<= LOG2_BITS_PER_UNIT; | |
718 | off += bitpos; | |
719 | off_cst = true; | |
720 | } | |
721 | /* If &X->a is equal to X, the range of X is the result. */ | |
722 | if (off_cst && known_eq (off, 0)) | |
c39cb6bf | 723 | return true; |
4c85ff75 AM |
724 | else if (flag_delete_null_pointer_checks |
725 | && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))) | |
726 | { | |
c39cb6bf JJ |
727 | /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't |
728 | allow going from non-NULL pointer to NULL. */ | |
729 | if (!range_includes_zero_p (&r)) | |
730 | { | |
731 | /* We could here instead adjust r by off >> LOG2_BITS_PER_UNIT | |
732 | using POINTER_PLUS_EXPR if off_cst and just fall back to | |
733 | this. */ | |
734 | r = range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt))); | |
735 | return true; | |
736 | } | |
4c85ff75 AM |
737 | } |
738 | /* If MEM_REF has a "positive" offset, consider it non-NULL | |
739 | always, for -fdelete-null-pointer-checks also "negative" | |
740 | ones. Punt for unknown offsets (e.g. variable ones). */ | |
741 | if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)) | |
742 | && off_cst | |
743 | && known_ne (off, 0) | |
744 | && (flag_delete_null_pointer_checks || known_gt (off, 0))) | |
745 | { | |
746 | r = range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt))); | |
747 | return true; | |
748 | } | |
749 | r = int_range<2> (TREE_TYPE (gimple_assign_rhs1 (stmt))); | |
750 | return true; | |
751 | } | |
752 | ||
753 | // Handle "= &a". | |
754 | if (tree_single_nonzero_warnv_p (expr, &strict_overflow_p)) | |
755 | { | |
756 | r = range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt))); | |
757 | return true; | |
758 | } | |
759 | ||
760 | // Otherwise return varying. | |
761 | r = int_range<2> (TREE_TYPE (gimple_assign_rhs1 (stmt))); | |
762 | return true; | |
763 | } | |
764 | ||
765 | // Calculate a range for phi statement S and return it in R. | |
766 | // If a range cannot be calculated, return false. | |
767 | ||
768 | bool | |
769 | fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src) | |
770 | { | |
771 | tree phi_def = gimple_phi_result (phi); | |
478cc962 | 772 | tree type = gimple_range_type (phi); |
4c85ff75 | 773 | int_range_max arg_range; |
661c02e5 | 774 | int_range_max equiv_range; |
4c85ff75 AM |
775 | unsigned x; |
776 | ||
478cc962 | 777 | if (!type) |
4c85ff75 AM |
778 | return false; |
779 | ||
73cf73af AM |
780 | // Track if all executable arguments are the same. |
781 | tree single_arg = NULL_TREE; | |
782 | bool seen_arg = false; | |
783 | ||
4c85ff75 AM |
784 | // Start with an empty range, unioning in each argument's range. |
785 | r.set_undefined (); | |
786 | for (x = 0; x < gimple_phi_num_args (phi); x++) | |
787 | { | |
788 | tree arg = gimple_phi_arg_def (phi, x); | |
6d936684 AM |
789 | // An argument that is the same as the def provides no new range. |
790 | if (arg == phi_def) | |
791 | continue; | |
792 | ||
4c85ff75 AM |
793 | edge e = gimple_phi_arg_edge (phi, x); |
794 | ||
4c85ff75 AM |
795 | // Get the range of the argument on its edge. |
796 | src.get_phi_operand (arg_range, arg, e); | |
73cf73af AM |
797 | |
798 | if (!arg_range.undefined_p ()) | |
799 | { | |
800 | // Register potential dependencies for stale value tracking. | |
e43b15c8 AM |
801 | // Likewise, if the incoming PHI argument is equivalent to this |
802 | // PHI definition, it provides no new info. Accumulate these ranges | |
803 | // in case all arguments are equivalences. | |
804 | if (src.query ()->query_relation (e, arg, phi_def, false) == EQ_EXPR) | |
805 | equiv_range.union_(arg_range); | |
806 | else | |
807 | r.union_ (arg_range); | |
808 | ||
73cf73af AM |
809 | if (gimple_range_ssa_p (arg) && src.gori ()) |
810 | src.gori ()->register_dependency (phi_def, arg); | |
811 | ||
812 | // Track if all arguments are the same. | |
813 | if (!seen_arg) | |
814 | { | |
815 | seen_arg = true; | |
816 | single_arg = arg; | |
817 | } | |
818 | else if (single_arg != arg) | |
819 | single_arg = NULL_TREE; | |
820 | } | |
821 | ||
4c85ff75 | 822 | // Once the value reaches varying, stop looking. |
73cf73af | 823 | if (r.varying_p () && single_arg == NULL_TREE) |
4c85ff75 AM |
824 | break; |
825 | } | |
826 | ||
661c02e5 AM |
827 | // If all arguments were equivalences, use the equivalence ranges as no |
828 | // arguments were processed. | |
e43b15c8 | 829 | if (r.undefined_p () && !equiv_range.undefined_p ()) |
661c02e5 AM |
830 | r = equiv_range; |
831 | ||
73cf73af AM |
832 | // If the PHI boils down to a single effective argument, look at it. |
833 | if (single_arg) | |
834 | { | |
835 | // Symbolic arguments are equivalences. | |
836 | if (gimple_range_ssa_p (single_arg)) | |
837 | src.register_relation (phi, EQ_EXPR, phi_def, single_arg); | |
838 | else if (src.get_operand (arg_range, single_arg) | |
839 | && arg_range.singleton_p ()) | |
840 | { | |
841 | // Numerical arguments that are a constant can be returned as | |
842 | // the constant. This can help fold later cases where even this | |
843 | // constant might have been UNDEFINED via an unreachable edge. | |
844 | r = arg_range; | |
845 | return true; | |
846 | } | |
847 | } | |
848 | ||
4c85ff75 | 849 | // If SCEV is available, query if this PHI has any knonwn values. |
00446916 | 850 | if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def))) |
4c85ff75 AM |
851 | { |
852 | value_range loop_range; | |
853 | class loop *l = loop_containing_stmt (phi); | |
854 | if (l && loop_outer (l)) | |
855 | { | |
856 | range_of_ssa_name_with_loop_info (loop_range, phi_def, l, phi, src); | |
857 | if (!loop_range.varying_p ()) | |
858 | { | |
859 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
860 | { | |
861 | fprintf (dump_file, " Loops range found for "); | |
862 | print_generic_expr (dump_file, phi_def, TDF_SLIM); | |
863 | fprintf (dump_file, ": "); | |
864 | loop_range.dump (dump_file); | |
865 | fprintf (dump_file, " and calculated range :"); | |
866 | r.dump (dump_file); | |
867 | fprintf (dump_file, "\n"); | |
868 | } | |
869 | r.intersect (loop_range); | |
870 | } | |
871 | } | |
872 | } | |
873 | ||
874 | return true; | |
875 | } | |
876 | ||
877 | // Calculate a range for call statement S and return it in R. | |
878 | // If a range cannot be calculated, return false. | |
879 | ||
880 | bool | |
881 | fold_using_range::range_of_call (irange &r, gcall *call, fur_source &src) | |
882 | { | |
478cc962 AM |
883 | tree type = gimple_range_type (call); |
884 | if (!type) | |
885 | return false; | |
886 | ||
4c85ff75 AM |
887 | tree lhs = gimple_call_lhs (call); |
888 | bool strict_overflow_p; | |
889 | ||
4c85ff75 AM |
890 | if (range_of_builtin_call (r, call, src)) |
891 | ; | |
892 | else if (gimple_stmt_nonnegative_warnv_p (call, &strict_overflow_p)) | |
893 | r.set (build_int_cst (type, 0), TYPE_MAX_VALUE (type)); | |
894 | else if (gimple_call_nonnull_result_p (call) | |
895 | || gimple_call_nonnull_arg (call)) | |
896 | r = range_nonzero (type); | |
897 | else | |
898 | r.set_varying (type); | |
899 | ||
900 | // If there is an LHS, intersect that with what is known. | |
901 | if (lhs) | |
902 | { | |
903 | value_range def; | |
904 | def = gimple_range_global (lhs); | |
905 | r.intersect (def); | |
906 | } | |
907 | return true; | |
908 | } | |
909 | ||
910 | // Return the range of a __builtin_ubsan* in CALL and set it in R. | |
911 | // CODE is the type of ubsan call (PLUS_EXPR, MINUS_EXPR or | |
912 | // MULT_EXPR). | |
913 | ||
914 | void | |
915 | fold_using_range::range_of_builtin_ubsan_call (irange &r, gcall *call, | |
916 | tree_code code, fur_source &src) | |
917 | { | |
918 | gcc_checking_assert (code == PLUS_EXPR || code == MINUS_EXPR | |
919 | || code == MULT_EXPR); | |
478cc962 | 920 | tree type = gimple_range_type (call); |
4c85ff75 AM |
921 | range_operator *op = range_op_handler (code, type); |
922 | gcc_checking_assert (op); | |
923 | int_range_max ir0, ir1; | |
924 | tree arg0 = gimple_call_arg (call, 0); | |
925 | tree arg1 = gimple_call_arg (call, 1); | |
926 | src.get_operand (ir0, arg0); | |
927 | src.get_operand (ir1, arg1); | |
9693ecdf AM |
928 | // Check for any relation between arg0 and arg1. |
929 | relation_kind relation = src.query_relation (arg0, arg1); | |
4c85ff75 AM |
930 | |
931 | bool saved_flag_wrapv = flag_wrapv; | |
932 | // Pretend the arithmetic is wrapping. If there is any overflow, | |
933 | // we'll complain, but will actually do wrapping operation. | |
934 | flag_wrapv = 1; | |
9693ecdf | 935 | op->fold_range (r, type, ir0, ir1, relation); |
4c85ff75 AM |
936 | flag_wrapv = saved_flag_wrapv; |
937 | ||
938 | // If for both arguments vrp_valueize returned non-NULL, this should | |
939 | // have been already folded and if not, it wasn't folded because of | |
940 | // overflow. Avoid removing the UBSAN_CHECK_* calls in that case. | |
941 | if (r.singleton_p ()) | |
942 | r.set_varying (type); | |
943 | } | |
944 | ||
d5a8c138 AM |
945 | // Return TRUE if we recognize the target character set and return the |
946 | // range for lower case and upper case letters. | |
947 | ||
948 | static bool | |
949 | get_letter_range (tree type, irange &lowers, irange &uppers) | |
950 | { | |
951 | // ASCII | |
952 | int a = lang_hooks.to_target_charset ('a'); | |
953 | int z = lang_hooks.to_target_charset ('z'); | |
954 | int A = lang_hooks.to_target_charset ('A'); | |
955 | int Z = lang_hooks.to_target_charset ('Z'); | |
956 | ||
957 | if ((z - a == 25) && (Z - A == 25)) | |
958 | { | |
959 | lowers = int_range<2> (build_int_cst (type, a), build_int_cst (type, z)); | |
960 | uppers = int_range<2> (build_int_cst (type, A), build_int_cst (type, Z)); | |
961 | return true; | |
962 | } | |
963 | // Unknown character set. | |
964 | return false; | |
965 | } | |
966 | ||
4c85ff75 AM |
967 | // For a builtin in CALL, return a range in R if known and return |
968 | // TRUE. Otherwise return FALSE. | |
969 | ||
970 | bool | |
971 | fold_using_range::range_of_builtin_call (irange &r, gcall *call, | |
972 | fur_source &src) | |
973 | { | |
974 | combined_fn func = gimple_call_combined_fn (call); | |
975 | if (func == CFN_LAST) | |
976 | return false; | |
977 | ||
478cc962 | 978 | tree type = gimple_range_type (call); |
4c85ff75 AM |
979 | tree arg; |
980 | int mini, maxi, zerov = 0, prec; | |
981 | scalar_int_mode mode; | |
982 | ||
983 | switch (func) | |
984 | { | |
985 | case CFN_BUILT_IN_CONSTANT_P: | |
4c85ff75 AM |
986 | arg = gimple_call_arg (call, 0); |
987 | if (src.get_operand (r, arg) && r.singleton_p ()) | |
988 | { | |
989 | r.set (build_one_cst (type), build_one_cst (type)); | |
990 | return true; | |
991 | } | |
b18394ce AM |
992 | if (cfun->after_inlining) |
993 | { | |
994 | r.set_zero (type); | |
995 | // r.equiv_clear (); | |
996 | return true; | |
997 | } | |
4c85ff75 AM |
998 | break; |
999 | ||
1ce0b26e AM |
1000 | case CFN_BUILT_IN_TOUPPER: |
1001 | { | |
1002 | arg = gimple_call_arg (call, 0); | |
c86c95ed AM |
1003 | // If the argument isn't compatible with the LHS, do nothing. |
1004 | if (!range_compatible_p (type, TREE_TYPE (arg))) | |
1005 | return false; | |
1ce0b26e AM |
1006 | if (!src.get_operand (r, arg)) |
1007 | return false; | |
d5a8c138 AM |
1008 | |
1009 | int_range<3> lowers; | |
1010 | int_range<3> uppers; | |
1011 | if (!get_letter_range (type, lowers, uppers)) | |
1012 | return false; | |
1013 | ||
1ce0b26e AM |
1014 | // Return the range passed in without any lower case characters, |
1015 | // but including all the upper case ones. | |
d5a8c138 AM |
1016 | lowers.invert (); |
1017 | r.intersect (lowers); | |
1ce0b26e AM |
1018 | r.union_ (uppers); |
1019 | return true; | |
1020 | } | |
1021 | ||
1022 | case CFN_BUILT_IN_TOLOWER: | |
1023 | { | |
1024 | arg = gimple_call_arg (call, 0); | |
c86c95ed AM |
1025 | // If the argument isn't compatible with the LHS, do nothing. |
1026 | if (!range_compatible_p (type, TREE_TYPE (arg))) | |
1027 | return false; | |
1ce0b26e AM |
1028 | if (!src.get_operand (r, arg)) |
1029 | return false; | |
d5a8c138 AM |
1030 | |
1031 | int_range<3> lowers; | |
1032 | int_range<3> uppers; | |
1033 | if (!get_letter_range (type, lowers, uppers)) | |
1034 | return false; | |
1035 | ||
1ce0b26e AM |
1036 | // Return the range passed in without any upper case characters, |
1037 | // but including all the lower case ones. | |
d5a8c138 AM |
1038 | uppers.invert (); |
1039 | r.intersect (uppers); | |
1ce0b26e AM |
1040 | r.union_ (lowers); |
1041 | return true; | |
1042 | } | |
1043 | ||
4c85ff75 AM |
1044 | CASE_CFN_FFS: |
1045 | CASE_CFN_POPCOUNT: | |
1046 | // __builtin_ffs* and __builtin_popcount* return [0, prec]. | |
1047 | arg = gimple_call_arg (call, 0); | |
1048 | prec = TYPE_PRECISION (TREE_TYPE (arg)); | |
1049 | mini = 0; | |
1050 | maxi = prec; | |
1051 | src.get_operand (r, arg); | |
1052 | // If arg is non-zero, then ffs or popcount are non-zero. | |
1053 | if (!range_includes_zero_p (&r)) | |
1054 | mini = 1; | |
1055 | // If some high bits are known to be zero, decrease the maximum. | |
1056 | if (!r.undefined_p ()) | |
1057 | { | |
1058 | if (TYPE_SIGN (r.type ()) == SIGNED) | |
1059 | range_cast (r, unsigned_type_for (r.type ())); | |
1060 | wide_int max = r.upper_bound (); | |
1061 | maxi = wi::floor_log2 (max) + 1; | |
1062 | } | |
1063 | r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); | |
1064 | return true; | |
1065 | ||
1066 | CASE_CFN_PARITY: | |
1067 | r.set (build_zero_cst (type), build_one_cst (type)); | |
1068 | return true; | |
1069 | ||
1070 | CASE_CFN_CLZ: | |
1071 | // __builtin_c[lt]z* return [0, prec-1], except when the | |
1072 | // argument is 0, but that is undefined behavior. | |
1073 | // | |
1074 | // For __builtin_c[lt]z* consider argument of 0 always undefined | |
1075 | // behavior, for internal fns depending on C?Z_DEFINED_VALUE_AT_ZERO. | |
1076 | arg = gimple_call_arg (call, 0); | |
1077 | prec = TYPE_PRECISION (TREE_TYPE (arg)); | |
1078 | mini = 0; | |
1079 | maxi = prec - 1; | |
1080 | mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg)); | |
1081 | if (gimple_call_internal_p (call)) | |
1082 | { | |
1083 | if (optab_handler (clz_optab, mode) != CODE_FOR_nothing | |
1084 | && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov) == 2) | |
1085 | { | |
1086 | // Only handle the single common value. | |
1087 | if (zerov == prec) | |
1088 | maxi = prec; | |
1089 | else | |
1090 | // Magic value to give up, unless we can prove arg is non-zero. | |
1091 | mini = -2; | |
1092 | } | |
1093 | } | |
1094 | ||
1095 | src.get_operand (r, arg); | |
1096 | // From clz of minimum we can compute result maximum. | |
1097 | if (!r.undefined_p ()) | |
1098 | { | |
1099 | // From clz of minimum we can compute result maximum. | |
1100 | if (wi::gt_p (r.lower_bound (), 0, TYPE_SIGN (r.type ()))) | |
1101 | { | |
1102 | maxi = prec - 1 - wi::floor_log2 (r.lower_bound ()); | |
1103 | if (mini == -2) | |
1104 | mini = 0; | |
1105 | } | |
1106 | else if (!range_includes_zero_p (&r)) | |
1107 | { | |
1108 | mini = 0; | |
1109 | maxi = prec - 1; | |
1110 | } | |
1111 | if (mini == -2) | |
1112 | break; | |
1113 | // From clz of maximum we can compute result minimum. | |
1114 | wide_int max = r.upper_bound (); | |
1115 | int newmini = prec - 1 - wi::floor_log2 (max); | |
1116 | if (max == 0) | |
1117 | { | |
1118 | // If CLZ_DEFINED_VALUE_AT_ZERO is 2 with VALUE of prec, | |
1119 | // return [prec, prec], otherwise ignore the range. | |
1120 | if (maxi == prec) | |
1121 | mini = prec; | |
1122 | } | |
1123 | else | |
1124 | mini = newmini; | |
1125 | } | |
1126 | if (mini == -2) | |
1127 | break; | |
1128 | r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); | |
1129 | return true; | |
1130 | ||
1131 | CASE_CFN_CTZ: | |
1132 | // __builtin_ctz* return [0, prec-1], except for when the | |
1133 | // argument is 0, but that is undefined behavior. | |
1134 | // | |
1135 | // For __builtin_ctz* consider argument of 0 always undefined | |
1136 | // behavior, for internal fns depending on CTZ_DEFINED_VALUE_AT_ZERO. | |
1137 | arg = gimple_call_arg (call, 0); | |
1138 | prec = TYPE_PRECISION (TREE_TYPE (arg)); | |
1139 | mini = 0; | |
1140 | maxi = prec - 1; | |
1141 | mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg)); | |
1142 | if (gimple_call_internal_p (call)) | |
1143 | { | |
1144 | if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing | |
1145 | && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov) == 2) | |
1146 | { | |
1147 | // Handle only the two common values. | |
1148 | if (zerov == -1) | |
1149 | mini = -1; | |
1150 | else if (zerov == prec) | |
1151 | maxi = prec; | |
1152 | else | |
1153 | // Magic value to give up, unless we can prove arg is non-zero. | |
1154 | mini = -2; | |
1155 | } | |
1156 | } | |
1157 | src.get_operand (r, arg); | |
1158 | if (!r.undefined_p ()) | |
1159 | { | |
1160 | // If arg is non-zero, then use [0, prec - 1]. | |
1161 | if (!range_includes_zero_p (&r)) | |
1162 | { | |
1163 | mini = 0; | |
1164 | maxi = prec - 1; | |
1165 | } | |
1166 | // If some high bits are known to be zero, we can decrease | |
1167 | // the maximum. | |
1168 | wide_int max = r.upper_bound (); | |
1169 | if (max == 0) | |
1170 | { | |
1171 | // Argument is [0, 0]. If CTZ_DEFINED_VALUE_AT_ZERO | |
1172 | // is 2 with value -1 or prec, return [-1, -1] or [prec, prec]. | |
1173 | // Otherwise ignore the range. | |
1174 | if (mini == -1) | |
1175 | maxi = -1; | |
1176 | else if (maxi == prec) | |
1177 | mini = prec; | |
1178 | } | |
1179 | // If value at zero is prec and 0 is in the range, we can't lower | |
1180 | // the upper bound. We could create two separate ranges though, | |
1181 | // [0,floor_log2(max)][prec,prec] though. | |
1182 | else if (maxi != prec) | |
1183 | maxi = wi::floor_log2 (max); | |
1184 | } | |
1185 | if (mini == -2) | |
1186 | break; | |
1187 | r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); | |
1188 | return true; | |
1189 | ||
1190 | CASE_CFN_CLRSB: | |
1191 | arg = gimple_call_arg (call, 0); | |
1192 | prec = TYPE_PRECISION (TREE_TYPE (arg)); | |
1193 | r.set (build_int_cst (type, 0), build_int_cst (type, prec - 1)); | |
1194 | return true; | |
1195 | case CFN_UBSAN_CHECK_ADD: | |
1196 | range_of_builtin_ubsan_call (r, call, PLUS_EXPR, src); | |
1197 | return true; | |
1198 | case CFN_UBSAN_CHECK_SUB: | |
1199 | range_of_builtin_ubsan_call (r, call, MINUS_EXPR, src); | |
1200 | return true; | |
1201 | case CFN_UBSAN_CHECK_MUL: | |
1202 | range_of_builtin_ubsan_call (r, call, MULT_EXPR, src); | |
1203 | return true; | |
1204 | ||
1205 | case CFN_GOACC_DIM_SIZE: | |
1206 | case CFN_GOACC_DIM_POS: | |
1207 | // Optimizing these two internal functions helps the loop | |
1208 | // optimizer eliminate outer comparisons. Size is [1,N] | |
1209 | // and pos is [0,N-1]. | |
1210 | { | |
1211 | bool is_pos = func == CFN_GOACC_DIM_POS; | |
1212 | int axis = oacc_get_ifn_dim_arg (call); | |
1213 | int size = oacc_get_fn_dim_size (current_function_decl, axis); | |
1214 | if (!size) | |
1215 | // If it's dynamic, the backend might know a hardware limitation. | |
1216 | size = targetm.goacc.dim_limit (axis); | |
1217 | ||
1218 | r.set (build_int_cst (type, is_pos ? 0 : 1), | |
1219 | size | |
1220 | ? build_int_cst (type, size - is_pos) : vrp_val_max (type)); | |
1221 | return true; | |
1222 | } | |
1223 | ||
1224 | case CFN_BUILT_IN_STRLEN: | |
1225 | if (tree lhs = gimple_call_lhs (call)) | |
1226 | if (ptrdiff_type_node | |
1227 | && (TYPE_PRECISION (ptrdiff_type_node) | |
1228 | == TYPE_PRECISION (TREE_TYPE (lhs)))) | |
1229 | { | |
1230 | tree type = TREE_TYPE (lhs); | |
1231 | tree max = vrp_val_max (ptrdiff_type_node); | |
1232 | wide_int wmax | |
1233 | = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); | |
1234 | tree range_min = build_zero_cst (type); | |
1235 | // To account for the terminating NULL, the maximum length | |
1236 | // is one less than the maximum array size, which in turn | |
1237 | // is one less than PTRDIFF_MAX (or SIZE_MAX where it's | |
1238 | // smaller than the former type). | |
1239 | // FIXME: Use max_object_size() - 1 here. | |
1240 | tree range_max = wide_int_to_tree (type, wmax - 2); | |
1241 | r.set (range_min, range_max); | |
1242 | return true; | |
1243 | } | |
1244 | break; | |
1245 | default: | |
1246 | break; | |
1247 | } | |
1248 | return false; | |
1249 | } | |
1250 | ||
1251 | ||
1252 | // Calculate a range for COND_EXPR statement S and return it in R. | |
1253 | // If a range cannot be calculated, return false. | |
1254 | ||
1255 | bool | |
1256 | fold_using_range::range_of_cond_expr (irange &r, gassign *s, fur_source &src) | |
1257 | { | |
1258 | int_range_max cond_range, range1, range2; | |
1259 | tree cond = gimple_assign_rhs1 (s); | |
1260 | tree op1 = gimple_assign_rhs2 (s); | |
1261 | tree op2 = gimple_assign_rhs3 (s); | |
1262 | ||
478cc962 AM |
1263 | tree type = gimple_range_type (s); |
1264 | if (!type) | |
4c85ff75 AM |
1265 | return false; |
1266 | ||
478cc962 AM |
1267 | gcc_checking_assert (gimple_assign_rhs_code (s) == COND_EXPR); |
1268 | gcc_checking_assert (range_compatible_p (TREE_TYPE (op1), TREE_TYPE (op2))); | |
4c85ff75 AM |
1269 | src.get_operand (cond_range, cond); |
1270 | src.get_operand (range1, op1); | |
1271 | src.get_operand (range2, op2); | |
1272 | ||
1273 | // If the condition is known, choose the appropriate expression. | |
1274 | if (cond_range.singleton_p ()) | |
1275 | { | |
1276 | // False, pick second operand. | |
1277 | if (cond_range.zero_p ()) | |
1278 | r = range2; | |
1279 | else | |
1280 | r = range1; | |
1281 | } | |
1282 | else | |
1283 | { | |
1284 | r = range1; | |
1285 | r.union_ (range2); | |
1286 | } | |
ea789238 AM |
1287 | gcc_checking_assert (r.undefined_p () |
1288 | || range_compatible_p (r.type (), type)); | |
4c85ff75 AM |
1289 | return true; |
1290 | } | |
1291 | ||
1292 | // If SCEV has any information about phi node NAME, return it as a range in R. | |
1293 | ||
1294 | void | |
1295 | fold_using_range::range_of_ssa_name_with_loop_info (irange &r, tree name, | |
1296 | class loop *l, gphi *phi, | |
1297 | fur_source &src) | |
1298 | { | |
1299 | gcc_checking_assert (TREE_CODE (name) == SSA_NAME); | |
1300 | tree min, max, type = TREE_TYPE (name); | |
1301 | if (bounds_of_var_in_loop (&min, &max, src.query (), l, phi, name)) | |
1302 | { | |
1303 | if (TREE_CODE (min) != INTEGER_CST) | |
1304 | { | |
1305 | if (src.query ()->range_of_expr (r, min, phi) && !r.undefined_p ()) | |
1306 | min = wide_int_to_tree (type, r.lower_bound ()); | |
1307 | else | |
1308 | min = vrp_val_min (type); | |
1309 | } | |
1310 | if (TREE_CODE (max) != INTEGER_CST) | |
1311 | { | |
1312 | if (src.query ()->range_of_expr (r, max, phi) && !r.undefined_p ()) | |
1313 | max = wide_int_to_tree (type, r.upper_bound ()); | |
1314 | else | |
1315 | max = vrp_val_max (type); | |
1316 | } | |
1317 | r.set (min, max); | |
1318 | } | |
1319 | else | |
1320 | r.set_varying (type); | |
1321 | } | |
1322 | ||
1323 | // ----------------------------------------------------------------------- | |
1324 | ||
1325 | // Check if an && or || expression can be folded based on relations. ie | |
1326 | // c_2 = a_6 > b_7 | |
1327 | // c_3 = a_6 < b_7 | |
1328 | // c_4 = c_2 && c_3 | |
1329 | // c_2 and c_3 can never be true at the same time, | |
1330 | // Therefore c_4 can always resolve to false based purely on the relations. | |
1331 | ||
1332 | void | |
1333 | fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s, | |
1334 | fur_source &src) | |
1335 | { | |
1336 | // No queries or already folded. | |
1337 | if (!src.gori () || !src.query ()->oracle () || lhs_range.singleton_p ()) | |
1338 | return; | |
1339 | ||
1340 | // Only care about AND and OR expressions. | |
1341 | enum tree_code code = gimple_expr_code (s); | |
1342 | bool is_and = false; | |
1343 | if (code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) | |
1344 | is_and = true; | |
1345 | else if (code != BIT_IOR_EXPR && code != TRUTH_OR_EXPR) | |
1346 | return; | |
1347 | ||
1348 | tree lhs = gimple_get_lhs (s); | |
1349 | tree ssa1 = gimple_range_ssa_p (gimple_range_operand1 (s)); | |
1350 | tree ssa2 = gimple_range_ssa_p (gimple_range_operand2 (s)); | |
1351 | ||
1352 | // Deal with || and && only when there is a full set of symbolics. | |
1353 | if (!lhs || !ssa1 || !ssa2 | |
1354 | || (TREE_CODE (TREE_TYPE (lhs)) != BOOLEAN_TYPE) | |
1355 | || (TREE_CODE (TREE_TYPE (ssa1)) != BOOLEAN_TYPE) | |
1356 | || (TREE_CODE (TREE_TYPE (ssa2)) != BOOLEAN_TYPE)) | |
1357 | return; | |
1358 | ||
1359 | // Now we know its a boolean AND or OR expression with boolean operands. | |
1360 | // Ideally we search dependencies for common names, and see what pops out. | |
1361 | // until then, simply try to resolve direct dependencies. | |
1362 | ||
1363 | // Both names will need to have 2 direct dependencies. | |
1364 | tree ssa1_dep2 = src.gori ()->depend2 (ssa1); | |
1365 | tree ssa2_dep2 = src.gori ()->depend2 (ssa2); | |
1366 | if (!ssa1_dep2 || !ssa2_dep2) | |
1367 | return; | |
1368 | ||
1369 | tree ssa1_dep1 = src.gori ()->depend1 (ssa1); | |
1370 | tree ssa2_dep1 = src.gori ()->depend1 (ssa2); | |
1371 | // Make sure they are the same dependencies, and detect the order of the | |
1372 | // relationship. | |
1373 | bool reverse_op2 = true; | |
1374 | if (ssa1_dep1 == ssa2_dep1 && ssa1_dep2 == ssa2_dep2) | |
1375 | reverse_op2 = false; | |
1376 | else if (ssa1_dep1 != ssa2_dep2 || ssa1_dep2 != ssa2_dep1) | |
1377 | return; | |
1378 | ||
1379 | range_operator *handler1 = gimple_range_handler (SSA_NAME_DEF_STMT (ssa1)); | |
1380 | range_operator *handler2 = gimple_range_handler (SSA_NAME_DEF_STMT (ssa2)); | |
1381 | ||
fe4e6c82 AM |
1382 | // If either handler is not present, no relation is found. |
1383 | if (!handler1 || !handler2) | |
1384 | return; | |
1385 | ||
4c85ff75 AM |
1386 | int_range<2> bool_one (boolean_true_node, boolean_true_node); |
1387 | ||
1388 | relation_kind relation1 = handler1->op1_op2_relation (bool_one); | |
1389 | relation_kind relation2 = handler2->op1_op2_relation (bool_one); | |
1390 | if (relation1 == VREL_NONE || relation2 == VREL_NONE) | |
1391 | return; | |
1392 | ||
1393 | if (reverse_op2) | |
1394 | relation2 = relation_negate (relation2); | |
1395 | ||
1396 | // x && y is false if the relation intersection of the true cases is NULL. | |
1397 | if (is_and && relation_intersect (relation1, relation2) == VREL_EMPTY) | |
1398 | lhs_range = int_range<2> (boolean_false_node, boolean_false_node); | |
1399 | // x || y is true if the union of the true cases is NO-RELATION.. | |
1400 | // ie, one or the other being true covers the full range of possibilties. | |
1401 | else if (!is_and && relation_union (relation1, relation2) == VREL_NONE) | |
1402 | lhs_range = bool_one; | |
1403 | else | |
1404 | return; | |
1405 | ||
1406 | range_cast (lhs_range, TREE_TYPE (lhs)); | |
1407 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1408 | { | |
1409 | fprintf (dump_file, " Relation adjustment: "); | |
1410 | print_generic_expr (dump_file, ssa1, TDF_SLIM); | |
1411 | fprintf (dump_file, " and "); | |
1412 | print_generic_expr (dump_file, ssa2, TDF_SLIM); | |
1413 | fprintf (dump_file, " combine to produce "); | |
1414 | lhs_range.dump (dump_file); | |
1415 | fputc ('\n', dump_file); | |
1416 | } | |
1417 | ||
1418 | return; | |
1419 | } | |
1420 | ||
1421 | // Register any outgoing edge relations from a conditional branch. | |
1422 | ||
1423 | void | |
198bc5ec | 1424 | fur_source::register_outgoing_edges (gcond *s, irange &lhs_range, edge e0, edge e1) |
4c85ff75 AM |
1425 | { |
1426 | int_range_max r; | |
a0accaa9 | 1427 | int_range<2> e0_range, e1_range; |
4c85ff75 AM |
1428 | tree name; |
1429 | range_operator *handler; | |
1430 | basic_block bb = gimple_bb (s); | |
1431 | ||
198bc5ec | 1432 | if (e0) |
a0accaa9 AM |
1433 | { |
1434 | // If this edge is never taken, ignore it. | |
1435 | gcond_edge_range (e0_range, e0); | |
1436 | e0_range.intersect (lhs_range); | |
1437 | if (e0_range.undefined_p ()) | |
1438 | e0 = NULL; | |
1439 | } | |
1440 | ||
4c85ff75 | 1441 | |
198bc5ec | 1442 | if (e1) |
a0accaa9 AM |
1443 | { |
1444 | // If this edge is never taken, ignore it. | |
1445 | gcond_edge_range (e1_range, e1); | |
1446 | e1_range.intersect (lhs_range); | |
1447 | if (e1_range.undefined_p ()) | |
1448 | e1 = NULL; | |
1449 | } | |
4c85ff75 | 1450 | |
4c85ff75 AM |
1451 | if (!e0 && !e1) |
1452 | return; | |
1453 | ||
1454 | // First, register the gcond itself. This will catch statements like | |
1455 | // if (a_2 < b_5) | |
1456 | tree ssa1 = gimple_range_ssa_p (gimple_range_operand1 (s)); | |
1457 | tree ssa2 = gimple_range_ssa_p (gimple_range_operand2 (s)); | |
1458 | if (ssa1 && ssa2) | |
1459 | { | |
1460 | handler = gimple_range_handler (s); | |
1461 | gcc_checking_assert (handler); | |
1462 | if (e0) | |
1463 | { | |
a0accaa9 | 1464 | relation_kind relation = handler->op1_op2_relation (e0_range); |
4c85ff75 | 1465 | if (relation != VREL_NONE) |
198bc5ec | 1466 | register_relation (e0, relation, ssa1, ssa2); |
4c85ff75 AM |
1467 | } |
1468 | if (e1) | |
1469 | { | |
a0accaa9 | 1470 | relation_kind relation = handler->op1_op2_relation (e1_range); |
4c85ff75 | 1471 | if (relation != VREL_NONE) |
198bc5ec | 1472 | register_relation (e1, relation, ssa1, ssa2); |
4c85ff75 AM |
1473 | } |
1474 | } | |
1475 | ||
1476 | // Outgoing relations of GORI exports require a gori engine. | |
198bc5ec | 1477 | if (!gori ()) |
4c85ff75 AM |
1478 | return; |
1479 | ||
4c85ff75 AM |
1480 | // Now look for other relations in the exports. This will find stmts |
1481 | // leading to the condition such as: | |
1482 | // c_2 = a_4 < b_7 | |
1483 | // if (c_2) | |
198bc5ec | 1484 | FOR_EACH_GORI_EXPORT_NAME (*(gori ()), bb, name) |
4c85ff75 AM |
1485 | { |
1486 | if (TREE_CODE (TREE_TYPE (name)) != BOOLEAN_TYPE) | |
1487 | continue; | |
1488 | gimple *stmt = SSA_NAME_DEF_STMT (name); | |
1489 | handler = gimple_range_handler (stmt); | |
1490 | if (!handler) | |
1491 | continue; | |
1492 | tree ssa1 = gimple_range_ssa_p (gimple_range_operand1 (stmt)); | |
1493 | tree ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt)); | |
1494 | if (ssa1 && ssa2) | |
1495 | { | |
198bc5ec | 1496 | if (e0 && gori ()->outgoing_edge_range_p (r, e0, name, *m_query) |
4c85ff75 AM |
1497 | && r.singleton_p ()) |
1498 | { | |
1499 | relation_kind relation = handler->op1_op2_relation (r); | |
1500 | if (relation != VREL_NONE) | |
198bc5ec | 1501 | register_relation (e0, relation, ssa1, ssa2); |
4c85ff75 | 1502 | } |
198bc5ec | 1503 | if (e1 && gori ()->outgoing_edge_range_p (r, e1, name, *m_query) |
4c85ff75 AM |
1504 | && r.singleton_p ()) |
1505 | { | |
1506 | relation_kind relation = handler->op1_op2_relation (r); | |
1507 | if (relation != VREL_NONE) | |
198bc5ec | 1508 | register_relation (e1, relation, ssa1, ssa2); |
4c85ff75 AM |
1509 | } |
1510 | } | |
1511 | } | |
1512 | } |