]>
Commit | Line | Data |
---|---|---|
4c85ff75 | 1 | /* Code for GIMPLE range related routines. |
a945c346 | 2 | Copyright (C) 2019-2024 Free Software Foundation, Inc. |
4c85ff75 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" | |
ba206889 | 32 | #include "gimple-iterator.h" |
4c85ff75 AM |
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" | |
d5a8c138 | 41 | #include "langhooks.h" |
4c85ff75 AM |
42 | #include "vr-values.h" |
43 | #include "range.h" | |
44 | #include "value-query.h" | |
51ce0638 | 45 | #include "gimple-range-op.h" |
e68c8280 | 46 | #include "gimple-range.h" |
53ba8d66 JH |
47 | #include "cgraph.h" |
48 | #include "alloc-pool.h" | |
49 | #include "symbol-summary.h" | |
50 | #include "ipa-utils.h" | |
c8742849 MJ |
51 | #include "sreal.h" |
52 | #include "ipa-cp.h" | |
53ba8d66 | 53 | #include "ipa-prop.h" |
4c85ff75 AM |
54 | // Construct a fur_source, and set the m_query field. |
55 | ||
56 | fur_source::fur_source (range_query *q) | |
57 | { | |
58 | if (q) | |
59 | m_query = q; | |
4c85ff75 | 60 | else |
b7a28c09 | 61 | m_query = get_range_query (cfun); |
4c85ff75 AM |
62 | m_gori = NULL; |
63 | } | |
64 | ||
65 | // Invoke range_of_expr on EXPR. | |
66 | ||
67 | bool | |
45c8523d | 68 | fur_source::get_operand (vrange &r, tree expr) |
4c85ff75 AM |
69 | { |
70 | return m_query->range_of_expr (r, expr); | |
71 | } | |
72 | ||
73 | // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current | |
74 | // range_query to get the range on the edge. | |
75 | ||
76 | bool | |
45c8523d | 77 | fur_source::get_phi_operand (vrange &r, tree expr, edge e) |
4c85ff75 AM |
78 | { |
79 | return m_query->range_on_edge (r, e, expr); | |
80 | } | |
81 | ||
82 | // Default is no relation. | |
83 | ||
84 | relation_kind | |
85 | fur_source::query_relation (tree op1 ATTRIBUTE_UNUSED, | |
86 | tree op2 ATTRIBUTE_UNUSED) | |
87 | { | |
ade5531c | 88 | return VREL_VARYING; |
4c85ff75 AM |
89 | } |
90 | ||
91 | // Default registers nothing. | |
92 | ||
93 | void | |
94 | fur_source::register_relation (gimple *s ATTRIBUTE_UNUSED, | |
95 | relation_kind k ATTRIBUTE_UNUSED, | |
96 | tree op1 ATTRIBUTE_UNUSED, | |
97 | tree op2 ATTRIBUTE_UNUSED) | |
98 | { | |
99 | } | |
100 | ||
101 | // Default registers nothing. | |
102 | ||
103 | void | |
104 | fur_source::register_relation (edge e ATTRIBUTE_UNUSED, | |
105 | relation_kind k ATTRIBUTE_UNUSED, | |
106 | tree op1 ATTRIBUTE_UNUSED, | |
107 | tree op2 ATTRIBUTE_UNUSED) | |
108 | { | |
109 | } | |
110 | ||
111 | // This version of fur_source will pick a range up off an edge. | |
112 | ||
113 | class fur_edge : public fur_source | |
114 | { | |
115 | public: | |
116 | fur_edge (edge e, range_query *q = NULL); | |
45c8523d AH |
117 | virtual bool get_operand (vrange &r, tree expr) override; |
118 | virtual bool get_phi_operand (vrange &r, tree expr, edge e) override; | |
4c85ff75 AM |
119 | private: |
120 | edge m_edge; | |
121 | }; | |
122 | ||
123 | // Instantiate an edge based fur_source. | |
124 | ||
125 | inline | |
126 | fur_edge::fur_edge (edge e, range_query *q) : fur_source (q) | |
127 | { | |
128 | m_edge = e; | |
129 | } | |
130 | ||
131 | // Get the value of EXPR on edge m_edge. | |
132 | ||
133 | bool | |
45c8523d | 134 | fur_edge::get_operand (vrange &r, tree expr) |
4c85ff75 AM |
135 | { |
136 | return m_query->range_on_edge (r, m_edge, expr); | |
137 | } | |
138 | ||
139 | // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current | |
140 | // range_query to get the range on the edge. | |
141 | ||
142 | bool | |
45c8523d | 143 | fur_edge::get_phi_operand (vrange &r, tree expr, edge e) |
4c85ff75 | 144 | { |
c46b5b0a | 145 | // Edge to edge recalculations not supported yet, until we sort it out. |
4c85ff75 AM |
146 | gcc_checking_assert (e == m_edge); |
147 | return m_query->range_on_edge (r, e, expr); | |
148 | } | |
149 | ||
150 | // Instantiate a stmt based fur_source. | |
151 | ||
152 | fur_stmt::fur_stmt (gimple *s, range_query *q) : fur_source (q) | |
153 | { | |
154 | m_stmt = s; | |
155 | } | |
156 | ||
c46b5b0a | 157 | // Retrieve range of EXPR as it occurs as a use on stmt M_STMT. |
4c85ff75 AM |
158 | |
159 | bool | |
45c8523d | 160 | fur_stmt::get_operand (vrange &r, tree expr) |
4c85ff75 AM |
161 | { |
162 | return m_query->range_of_expr (r, expr, m_stmt); | |
163 | } | |
164 | ||
165 | // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current | |
166 | // range_query to get the range on the edge. | |
167 | ||
168 | bool | |
45c8523d | 169 | fur_stmt::get_phi_operand (vrange &r, tree expr, edge e) |
4c85ff75 AM |
170 | { |
171 | // Pick up the range of expr from edge E. | |
172 | fur_edge e_src (e, m_query); | |
173 | return e_src.get_operand (r, expr); | |
174 | } | |
175 | ||
176 | // Return relation based from m_stmt. | |
177 | ||
178 | relation_kind | |
179 | fur_stmt::query_relation (tree op1, tree op2) | |
180 | { | |
181 | return m_query->query_relation (m_stmt, op1, op2); | |
182 | } | |
183 | ||
184 | // Instantiate a stmt based fur_source with a GORI object. | |
185 | ||
186 | ||
187 | fur_depend::fur_depend (gimple *s, gori_compute *gori, range_query *q) | |
188 | : fur_stmt (s, q) | |
189 | { | |
190 | gcc_checking_assert (gori); | |
191 | m_gori = gori; | |
192 | // Set relations if there is an oracle in the range_query. | |
193 | // This will enable registering of relationships as they are discovered. | |
194 | m_oracle = q->oracle (); | |
195 | ||
196 | } | |
197 | ||
198 | // Register a relation on a stmt if there is an oracle. | |
199 | ||
200 | void | |
201 | fur_depend::register_relation (gimple *s, relation_kind k, tree op1, tree op2) | |
202 | { | |
203 | if (m_oracle) | |
3674d8e6 | 204 | m_oracle->register_stmt (s, k, op1, op2); |
4c85ff75 AM |
205 | } |
206 | ||
207 | // Register a relation on an edge if there is an oracle. | |
208 | ||
209 | void | |
210 | fur_depend::register_relation (edge e, relation_kind k, tree op1, tree op2) | |
211 | { | |
212 | if (m_oracle) | |
3674d8e6 | 213 | m_oracle->register_edge (e, k, op1, op2); |
4c85ff75 AM |
214 | } |
215 | ||
216 | // This version of fur_source will pick a range up from a list of ranges | |
217 | // supplied by the caller. | |
218 | ||
219 | class fur_list : public fur_source | |
220 | { | |
221 | public: | |
04859bda AM |
222 | fur_list (vrange &r1, range_query *q = NULL); |
223 | fur_list (vrange &r1, vrange &r2, range_query *q = NULL); | |
224 | fur_list (unsigned num, vrange **list, range_query *q = NULL); | |
45c8523d AH |
225 | virtual bool get_operand (vrange &r, tree expr) override; |
226 | virtual bool get_phi_operand (vrange &r, tree expr, edge e) override; | |
4c85ff75 | 227 | private: |
45c8523d AH |
228 | vrange *m_local[2]; |
229 | vrange **m_list; | |
4c85ff75 AM |
230 | unsigned m_index; |
231 | unsigned m_limit; | |
232 | }; | |
233 | ||
234 | // One range supplied for unary operations. | |
235 | ||
04859bda | 236 | fur_list::fur_list (vrange &r1, range_query *q) : fur_source (q) |
4c85ff75 AM |
237 | { |
238 | m_list = m_local; | |
239 | m_index = 0; | |
240 | m_limit = 1; | |
45c8523d | 241 | m_local[0] = &r1; |
4c85ff75 AM |
242 | } |
243 | ||
244 | // Two ranges supplied for binary operations. | |
245 | ||
04859bda | 246 | fur_list::fur_list (vrange &r1, vrange &r2, range_query *q) : fur_source (q) |
4c85ff75 AM |
247 | { |
248 | m_list = m_local; | |
249 | m_index = 0; | |
250 | m_limit = 2; | |
45c8523d AH |
251 | m_local[0] = &r1; |
252 | m_local[1] = &r2; | |
4c85ff75 AM |
253 | } |
254 | ||
255 | // Arbitrary number of ranges in a vector. | |
256 | ||
04859bda AM |
257 | fur_list::fur_list (unsigned num, vrange **list, range_query *q) |
258 | : fur_source (q) | |
4c85ff75 AM |
259 | { |
260 | m_list = list; | |
261 | m_index = 0; | |
262 | m_limit = num; | |
263 | } | |
264 | ||
265 | // Get the next operand from the vector, ensure types are compatible. | |
266 | ||
267 | bool | |
45c8523d | 268 | fur_list::get_operand (vrange &r, tree expr) |
4c85ff75 | 269 | { |
b769811e AM |
270 | // Do not use the vector for non-ssa-names, or if it has been emptied. |
271 | if (TREE_CODE (expr) != SSA_NAME || m_index >= m_limit) | |
4c85ff75 | 272 | return m_query->range_of_expr (r, expr); |
45c8523d | 273 | r = *m_list[m_index++]; |
4c85ff75 AM |
274 | gcc_checking_assert (range_compatible_p (TREE_TYPE (expr), r.type ())); |
275 | return true; | |
276 | } | |
277 | ||
278 | // This will simply pick the next operand from the vector. | |
279 | bool | |
45c8523d | 280 | fur_list::get_phi_operand (vrange &r, tree expr, edge e ATTRIBUTE_UNUSED) |
4c85ff75 AM |
281 | { |
282 | return get_operand (r, expr); | |
283 | } | |
284 | ||
285 | // Fold stmt S into range R using R1 as the first operand. | |
286 | ||
287 | bool | |
04859bda | 288 | fold_range (vrange &r, gimple *s, vrange &r1, range_query *q) |
4c85ff75 AM |
289 | { |
290 | fold_using_range f; | |
04859bda | 291 | fur_list src (r1, q); |
4c85ff75 AM |
292 | return f.fold_stmt (r, s, src); |
293 | } | |
294 | ||
295 | // Fold stmt S into range R using R1 and R2 as the first two operands. | |
296 | ||
297 | bool | |
04859bda | 298 | fold_range (vrange &r, gimple *s, vrange &r1, vrange &r2, range_query *q) |
4c85ff75 AM |
299 | { |
300 | fold_using_range f; | |
04859bda | 301 | fur_list src (r1, r2, q); |
4c85ff75 AM |
302 | return f.fold_stmt (r, s, src); |
303 | } | |
304 | ||
305 | // Fold stmt S into range R using NUM_ELEMENTS from VECTOR as the initial | |
306 | // operands encountered. | |
307 | ||
308 | bool | |
04859bda AM |
309 | fold_range (vrange &r, gimple *s, unsigned num_elements, vrange **vector, |
310 | range_query *q) | |
4c85ff75 AM |
311 | { |
312 | fold_using_range f; | |
04859bda | 313 | fur_list src (num_elements, vector, q); |
4c85ff75 AM |
314 | return f.fold_stmt (r, s, src); |
315 | } | |
316 | ||
317 | // Fold stmt S into range R using range query Q. | |
318 | ||
319 | bool | |
45c8523d | 320 | fold_range (vrange &r, gimple *s, range_query *q) |
4c85ff75 AM |
321 | { |
322 | fold_using_range f; | |
323 | fur_stmt src (s, q); | |
324 | return f.fold_stmt (r, s, src); | |
325 | } | |
326 | ||
327 | // Recalculate stmt S into R using range query Q as if it were on edge ON_EDGE. | |
328 | ||
329 | bool | |
45c8523d | 330 | fold_range (vrange &r, gimple *s, edge on_edge, range_query *q) |
4c85ff75 AM |
331 | { |
332 | fold_using_range f; | |
333 | fur_edge src (on_edge, q); | |
334 | return f.fold_stmt (r, s, src); | |
335 | } | |
336 | ||
04859bda AM |
337 | // Provide a fur_source which can be used to determine any relations on |
338 | // a statement. It manages the callback from fold_using_ranges to determine | |
339 | // a relation_trio for a statement. | |
340 | ||
341 | class fur_relation : public fur_stmt | |
342 | { | |
343 | public: | |
344 | fur_relation (gimple *s, range_query *q = NULL); | |
345 | virtual void register_relation (gimple *stmt, relation_kind k, tree op1, | |
346 | tree op2); | |
347 | virtual void register_relation (edge e, relation_kind k, tree op1, | |
348 | tree op2); | |
349 | relation_trio trio() const; | |
350 | private: | |
351 | relation_kind def_op1, def_op2, op1_op2; | |
352 | }; | |
353 | ||
354 | fur_relation::fur_relation (gimple *s, range_query *q) : fur_stmt (s, q) | |
355 | { | |
356 | def_op1 = def_op2 = op1_op2 = VREL_VARYING; | |
357 | } | |
358 | ||
359 | // Construct a trio from what is known. | |
360 | ||
361 | relation_trio | |
362 | fur_relation::trio () const | |
363 | { | |
364 | return relation_trio (def_op1, def_op2, op1_op2); | |
365 | } | |
366 | ||
367 | // Don't support edges, but avoid a compiler warning by providing the routine. | |
368 | ||
369 | void | |
370 | fur_relation::register_relation (edge, relation_kind, tree, tree) | |
371 | { | |
372 | } | |
373 | ||
374 | // Register relation K between OP1 and OP2 on STMT. | |
375 | ||
376 | void | |
377 | fur_relation::register_relation (gimple *stmt, relation_kind k, tree op1, | |
378 | tree op2) | |
379 | { | |
380 | tree lhs = gimple_get_lhs (stmt); | |
381 | tree a1 = NULL_TREE; | |
382 | tree a2 = NULL_TREE; | |
383 | switch (gimple_code (stmt)) | |
384 | { | |
385 | case GIMPLE_COND: | |
386 | a1 = gimple_cond_lhs (stmt); | |
387 | a2 = gimple_cond_rhs (stmt); | |
388 | break; | |
389 | case GIMPLE_ASSIGN: | |
390 | a1 = gimple_assign_rhs1 (stmt); | |
391 | if (gimple_num_ops (stmt) >= 3) | |
392 | a2 = gimple_assign_rhs2 (stmt); | |
393 | break; | |
394 | default: | |
395 | break; | |
396 | } | |
397 | // STMT is of the form LHS = A1 op A2, now map the relation to these | |
398 | // operands, if possible. | |
399 | if (op1 == lhs) | |
400 | { | |
401 | if (op2 == a1) | |
402 | def_op1 = k; | |
403 | else if (op2 == a2) | |
404 | def_op2 = k; | |
405 | } | |
406 | else if (op2 == lhs) | |
407 | { | |
408 | if (op1 == a1) | |
409 | def_op1 = relation_swap (k); | |
410 | else if (op1 == a2) | |
411 | def_op2 = relation_swap (k); | |
412 | } | |
413 | else | |
414 | { | |
415 | if (op1 == a1 && op2 == a2) | |
416 | op1_op2 = k; | |
417 | else if (op2 == a1 && op1 == a2) | |
418 | op1_op2 = relation_swap (k); | |
419 | } | |
420 | } | |
421 | ||
422 | // Return the relation trio for stmt S using query Q. | |
423 | ||
424 | relation_trio | |
425 | fold_relations (gimple *s, range_query *q) | |
426 | { | |
427 | fold_using_range f; | |
428 | fur_relation src (s, q); | |
429 | tree lhs = gimple_range_ssa_p (gimple_get_lhs (s)); | |
430 | if (lhs) | |
431 | { | |
432 | Value_Range vr(TREE_TYPE (lhs)); | |
433 | if (f.fold_stmt (vr, s, src)) | |
434 | return src.trio (); | |
435 | } | |
436 | return TRIO_VARYING; | |
437 | } | |
438 | ||
4c85ff75 AM |
439 | // ------------------------------------------------------------------------- |
440 | ||
441 | // Adjust the range for a pointer difference where the operands came | |
442 | // from a memchr. | |
443 | // | |
444 | // This notices the following sequence: | |
445 | // | |
446 | // def = __builtin_memchr (arg, 0, sz) | |
447 | // n = def - arg | |
448 | // | |
449 | // The range for N can be narrowed to [0, PTRDIFF_MAX - 1]. | |
450 | ||
451 | static void | |
452 | adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt) | |
453 | { | |
454 | tree op0 = gimple_assign_rhs1 (diff_stmt); | |
455 | tree op1 = gimple_assign_rhs2 (diff_stmt); | |
456 | tree op0_ptype = TREE_TYPE (TREE_TYPE (op0)); | |
457 | tree op1_ptype = TREE_TYPE (TREE_TYPE (op1)); | |
458 | gimple *call; | |
459 | ||
460 | if (TREE_CODE (op0) == SSA_NAME | |
461 | && TREE_CODE (op1) == SSA_NAME | |
462 | && (call = SSA_NAME_DEF_STMT (op0)) | |
463 | && is_gimple_call (call) | |
464 | && gimple_call_builtin_p (call, BUILT_IN_MEMCHR) | |
465 | && TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node) | |
466 | && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node) | |
467 | && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node) | |
468 | && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node) | |
469 | && gimple_call_builtin_p (call, BUILT_IN_MEMCHR) | |
470 | && vrp_operand_equal_p (op1, gimple_call_arg (call, 0)) | |
471 | && integer_zerop (gimple_call_arg (call, 1))) | |
472 | { | |
8b2181a4 AH |
473 | wide_int maxm1 = irange_val_max (ptrdiff_type_node) - 1; |
474 | res.intersect (int_range<2> (ptrdiff_type_node, | |
475 | wi::zero (TYPE_PRECISION (ptrdiff_type_node)), | |
476 | maxm1)); | |
4c85ff75 AM |
477 | } |
478 | } | |
479 | ||
bccf4b88 AH |
480 | // Adjust the range for an IMAGPART_EXPR. |
481 | ||
482 | static void | |
45c8523d | 483 | adjust_imagpart_expr (vrange &res, const gimple *stmt) |
bccf4b88 AH |
484 | { |
485 | tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); | |
486 | ||
487 | if (TREE_CODE (name) != SSA_NAME || !SSA_NAME_DEF_STMT (name)) | |
488 | return; | |
489 | ||
490 | gimple *def_stmt = SSA_NAME_DEF_STMT (name); | |
491 | if (is_gimple_call (def_stmt) && gimple_call_internal_p (def_stmt)) | |
492 | { | |
493 | switch (gimple_call_internal_fn (def_stmt)) | |
494 | { | |
495 | case IFN_ADD_OVERFLOW: | |
496 | case IFN_SUB_OVERFLOW: | |
497 | case IFN_MUL_OVERFLOW: | |
43a3252c JJ |
498 | case IFN_UADDC: |
499 | case IFN_USUBC: | |
bccf4b88 AH |
500 | case IFN_ATOMIC_COMPARE_EXCHANGE: |
501 | { | |
502 | int_range<2> r; | |
503 | r.set_varying (boolean_type_node); | |
504 | tree type = TREE_TYPE (gimple_assign_lhs (stmt)); | |
505 | range_cast (r, type); | |
506 | res.intersect (r); | |
507 | } | |
508 | default: | |
509 | break; | |
510 | } | |
511 | return; | |
512 | } | |
d44dc131 JJ |
513 | if (is_gimple_assign (def_stmt) |
514 | && gimple_assign_rhs_code (def_stmt) == COMPLEX_CST) | |
bccf4b88 AH |
515 | { |
516 | tree cst = gimple_assign_rhs1 (def_stmt); | |
6c121a2c AM |
517 | if (TREE_CODE (cst) == COMPLEX_CST |
518 | && TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) == INTEGER_TYPE) | |
bccf4b88 | 519 | { |
cb779afe AH |
520 | wide_int w = wi::to_wide (TREE_IMAGPART (cst)); |
521 | int_range<1> imag (TREE_TYPE (TREE_IMAGPART (cst)), w, w); | |
71f2928e | 522 | res.intersect (imag); |
bccf4b88 AH |
523 | } |
524 | } | |
525 | } | |
526 | ||
527 | // Adjust the range for a REALPART_EXPR. | |
528 | ||
529 | static void | |
45c8523d | 530 | adjust_realpart_expr (vrange &res, const gimple *stmt) |
bccf4b88 AH |
531 | { |
532 | tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); | |
533 | ||
534 | if (TREE_CODE (name) != SSA_NAME) | |
535 | return; | |
536 | ||
537 | gimple *def_stmt = SSA_NAME_DEF_STMT (name); | |
538 | if (!SSA_NAME_DEF_STMT (name)) | |
539 | return; | |
540 | ||
d44dc131 JJ |
541 | if (is_gimple_assign (def_stmt) |
542 | && gimple_assign_rhs_code (def_stmt) == COMPLEX_CST) | |
bccf4b88 AH |
543 | { |
544 | tree cst = gimple_assign_rhs1 (def_stmt); | |
6c121a2c AM |
545 | if (TREE_CODE (cst) == COMPLEX_CST |
546 | && TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) == INTEGER_TYPE) | |
bccf4b88 | 547 | { |
cb779afe AH |
548 | wide_int imag = wi::to_wide (TREE_REALPART (cst)); |
549 | int_range<2> tmp (TREE_TYPE (TREE_REALPART (cst)), imag, imag); | |
bccf4b88 AH |
550 | res.intersect (tmp); |
551 | } | |
552 | } | |
553 | } | |
554 | ||
4c85ff75 | 555 | // This function looks for situations when walking the use/def chains |
c46b5b0a | 556 | // may provide additional contextual range information not exposed on |
bccf4b88 | 557 | // this statement. |
4c85ff75 AM |
558 | |
559 | static void | |
45c8523d | 560 | gimple_range_adjustment (vrange &res, const gimple *stmt) |
4c85ff75 AM |
561 | { |
562 | switch (gimple_expr_code (stmt)) | |
563 | { | |
564 | case POINTER_DIFF_EXPR: | |
45c8523d | 565 | adjust_pointer_diff_expr (as_a <irange> (res), stmt); |
4c85ff75 AM |
566 | return; |
567 | ||
568 | case IMAGPART_EXPR: | |
bccf4b88 AH |
569 | adjust_imagpart_expr (res, stmt); |
570 | return; | |
571 | ||
572 | case REALPART_EXPR: | |
573 | adjust_realpart_expr (res, stmt); | |
574 | return; | |
4c85ff75 AM |
575 | |
576 | default: | |
577 | break; | |
578 | } | |
579 | } | |
580 | ||
4c85ff75 AM |
581 | // Calculate a range for statement S and return it in R. If NAME is provided it |
582 | // represents the SSA_NAME on the LHS of the statement. It is only required | |
583 | // if there is more than one lhs/output. If a range cannot | |
584 | // be calculated, return false. | |
585 | ||
586 | bool | |
45c8523d | 587 | fold_using_range::fold_stmt (vrange &r, gimple *s, fur_source &src, tree name) |
4c85ff75 AM |
588 | { |
589 | bool res = false; | |
590 | // If name and S are specified, make sure it is an LHS of S. | |
591 | gcc_checking_assert (!name || !gimple_get_lhs (s) || | |
592 | name == gimple_get_lhs (s)); | |
593 | ||
594 | if (!name) | |
595 | name = gimple_get_lhs (s); | |
596 | ||
597 | // Process addresses. | |
598 | if (gimple_code (s) == GIMPLE_ASSIGN | |
599 | && gimple_assign_rhs_code (s) == ADDR_EXPR) | |
36e87799 | 600 | return range_of_address (as_a <prange> (r), s, src); |
4c85ff75 | 601 | |
51ce0638 AM |
602 | gimple_range_op_handler handler (s); |
603 | if (handler) | |
604 | res = range_of_range_op (r, handler, src); | |
4c85ff75 AM |
605 | else if (is_a<gphi *>(s)) |
606 | res = range_of_phi (r, as_a<gphi *> (s), src); | |
607 | else if (is_a<gcall *>(s)) | |
608 | res = range_of_call (r, as_a<gcall *> (s), src); | |
609 | else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR) | |
610 | res = range_of_cond_expr (r, as_a<gassign *> (s), src); | |
611 | ||
a87819b8 AM |
612 | // If the result is varying, check for basic nonnegativeness. |
613 | // Specifically this helps for now with strict enum in cases like | |
614 | // g++.dg/warn/pr33738.C. | |
615 | bool so_p; | |
616 | if (res && r.varying_p () && INTEGRAL_TYPE_P (r.type ()) | |
617 | && gimple_stmt_nonnegative_warnv_p (s, &so_p)) | |
618 | r.set_nonnegative (r.type ()); | |
619 | ||
4c85ff75 AM |
620 | if (!res) |
621 | { | |
478cc962 AM |
622 | // If no name specified or range is unsupported, bail. |
623 | if (!name || !gimple_range_ssa_p (name)) | |
4c85ff75 AM |
624 | return false; |
625 | // We don't understand the stmt, so return the global range. | |
45c8523d | 626 | gimple_range_global (r, name); |
4c85ff75 AM |
627 | return true; |
628 | } | |
629 | ||
630 | if (r.undefined_p ()) | |
631 | return true; | |
632 | ||
633 | // We sometimes get compatible types copied from operands, make sure | |
634 | // the correct type is being returned. | |
635 | if (name && TREE_TYPE (name) != r.type ()) | |
636 | { | |
637 | gcc_checking_assert (range_compatible_p (r.type (), TREE_TYPE (name))); | |
638 | range_cast (r, TREE_TYPE (name)); | |
639 | } | |
640 | return true; | |
641 | } | |
642 | ||
643 | // Calculate a range for range_op statement S and return it in R. If any | |
644 | // If a range cannot be calculated, return false. | |
645 | ||
646 | bool | |
51ce0638 AM |
647 | fold_using_range::range_of_range_op (vrange &r, |
648 | gimple_range_op_handler &handler, | |
649 | fur_source &src) | |
4c85ff75 | 650 | { |
51ce0638 AM |
651 | gcc_checking_assert (handler); |
652 | gimple *s = handler.stmt (); | |
478cc962 AM |
653 | tree type = gimple_range_type (s); |
654 | if (!type) | |
655 | return false; | |
4c85ff75 | 656 | |
51ce0638 AM |
657 | tree lhs = handler.lhs (); |
658 | tree op1 = handler.operand1 (); | |
659 | tree op2 = handler.operand2 (); | |
5608e410 AM |
660 | |
661 | // Certain types of builtin functions may have no arguments. | |
662 | if (!op1) | |
663 | { | |
664 | Value_Range r1 (type); | |
665 | if (!handler.fold_range (r, type, r1, r1)) | |
666 | r.set_varying (type); | |
667 | return true; | |
668 | } | |
669 | ||
45c8523d AH |
670 | Value_Range range1 (TREE_TYPE (op1)); |
671 | Value_Range range2 (op2 ? TREE_TYPE (op2) : TREE_TYPE (op1)); | |
4c85ff75 AM |
672 | |
673 | if (src.get_operand (range1, op1)) | |
674 | { | |
675 | if (!op2) | |
676 | { | |
677 | // Fold range, and register any dependency if available. | |
45c8523d AH |
678 | Value_Range r2 (type); |
679 | r2.set_varying (type); | |
2f92f685 AM |
680 | if (!handler.fold_range (r, type, range1, r2)) |
681 | r.set_varying (type); | |
4c85ff75 AM |
682 | if (lhs && gimple_range_ssa_p (op1)) |
683 | { | |
684 | if (src.gori ()) | |
685 | src.gori ()->register_dependency (lhs, op1); | |
686 | relation_kind rel; | |
cf5bea76 | 687 | rel = handler.lhs_op1_relation (r, range1, range1); |
ade5531c | 688 | if (rel != VREL_VARYING) |
4c85ff75 AM |
689 | src.register_relation (s, rel, lhs, op1); |
690 | } | |
691 | } | |
692 | else if (src.get_operand (range2, op2)) | |
693 | { | |
694 | relation_kind rel = src.query_relation (op1, op2); | |
ade5531c | 695 | if (dump_file && (dump_flags & TDF_DETAILS) && rel != VREL_VARYING) |
4c85ff75 AM |
696 | { |
697 | fprintf (dump_file, " folding with relation "); | |
2f0b6a97 | 698 | print_generic_expr (dump_file, op1, TDF_SLIM); |
4c85ff75 | 699 | print_relation (dump_file, rel); |
2f0b6a97 | 700 | print_generic_expr (dump_file, op2, TDF_SLIM); |
4c85ff75 AM |
701 | fputc ('\n', dump_file); |
702 | } | |
703 | // Fold range, and register any dependency if available. | |
b565ac19 AM |
704 | if (!handler.fold_range (r, type, range1, range2, |
705 | relation_trio::op1_op2 (rel))) | |
2f92f685 | 706 | r.set_varying (type); |
a9058b08 | 707 | if (irange::supports_p (type)) |
9fedc3c0 | 708 | relation_fold_and_or (as_a <irange> (r), s, src, range1, range2); |
4c85ff75 AM |
709 | if (lhs) |
710 | { | |
711 | if (src.gori ()) | |
712 | { | |
713 | src.gori ()->register_dependency (lhs, op1); | |
714 | src.gori ()->register_dependency (lhs, op2); | |
715 | } | |
716 | if (gimple_range_ssa_p (op1)) | |
717 | { | |
cf5bea76 | 718 | rel = handler.lhs_op1_relation (r, range1, range2, rel); |
ade5531c | 719 | if (rel != VREL_VARYING) |
4c85ff75 AM |
720 | src.register_relation (s, rel, lhs, op1); |
721 | } | |
722 | if (gimple_range_ssa_p (op2)) | |
723 | { | |
b565ac19 | 724 | rel = handler.lhs_op2_relation (r, range1, range2, rel); |
ade5531c | 725 | if (rel != VREL_VARYING) |
4c85ff75 AM |
726 | src.register_relation (s, rel, lhs, op2); |
727 | } | |
728 | } | |
fec75ab8 AH |
729 | // Check for an existing BB, as we maybe asked to fold an |
730 | // artificial statement not in the CFG. | |
731 | else if (is_a<gcond *> (s) && gimple_bb (s)) | |
198bc5ec AH |
732 | { |
733 | basic_block bb = gimple_bb (s); | |
734 | edge e0 = EDGE_SUCC (bb, 0); | |
735 | edge e1 = EDGE_SUCC (bb, 1); | |
736 | ||
737 | if (!single_pred_p (e0->dest)) | |
738 | e0 = NULL; | |
739 | if (!single_pred_p (e1->dest)) | |
740 | e1 = NULL; | |
45c8523d AH |
741 | src.register_outgoing_edges (as_a<gcond *> (s), |
742 | as_a <irange> (r), e0, e1); | |
198bc5ec | 743 | } |
4c85ff75 AM |
744 | } |
745 | else | |
746 | r.set_varying (type); | |
747 | } | |
748 | else | |
749 | r.set_varying (type); | |
750 | // Make certain range-op adjustments that aren't handled any other way. | |
751 | gimple_range_adjustment (r, s); | |
752 | return true; | |
753 | } | |
754 | ||
755 | // Calculate the range of an assignment containing an ADDR_EXPR. | |
756 | // Return the range in R. | |
757 | // If a range cannot be calculated, set it to VARYING and return true. | |
758 | ||
759 | bool | |
36e87799 | 760 | fold_using_range::range_of_address (prange &r, gimple *stmt, fur_source &src) |
4c85ff75 AM |
761 | { |
762 | gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN); | |
763 | gcc_checking_assert (gimple_assign_rhs_code (stmt) == ADDR_EXPR); | |
764 | ||
765 | bool strict_overflow_p; | |
766 | tree expr = gimple_assign_rhs1 (stmt); | |
767 | poly_int64 bitsize, bitpos; | |
768 | tree offset; | |
769 | machine_mode mode; | |
770 | int unsignedp, reversep, volatilep; | |
771 | tree base = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, | |
772 | &bitpos, &offset, &mode, &unsignedp, | |
773 | &reversep, &volatilep); | |
774 | ||
775 | ||
776 | if (base != NULL_TREE | |
777 | && TREE_CODE (base) == MEM_REF | |
778 | && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) | |
779 | { | |
780 | tree ssa = TREE_OPERAND (base, 0); | |
781 | tree lhs = gimple_get_lhs (stmt); | |
782 | if (lhs && gimple_range_ssa_p (ssa) && src.gori ()) | |
783 | src.gori ()->register_dependency (lhs, ssa); | |
4c85ff75 AM |
784 | src.get_operand (r, ssa); |
785 | range_cast (r, TREE_TYPE (gimple_assign_rhs1 (stmt))); | |
786 | ||
787 | poly_offset_int off = 0; | |
788 | bool off_cst = false; | |
789 | if (offset == NULL_TREE || TREE_CODE (offset) == INTEGER_CST) | |
790 | { | |
791 | off = mem_ref_offset (base); | |
792 | if (offset) | |
793 | off += poly_offset_int::from (wi::to_poly_wide (offset), | |
794 | SIGNED); | |
795 | off <<= LOG2_BITS_PER_UNIT; | |
796 | off += bitpos; | |
797 | off_cst = true; | |
798 | } | |
799 | /* If &X->a is equal to X, the range of X is the result. */ | |
800 | if (off_cst && known_eq (off, 0)) | |
c39cb6bf | 801 | return true; |
4c85ff75 AM |
802 | else if (flag_delete_null_pointer_checks |
803 | && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))) | |
804 | { | |
c39cb6bf JJ |
805 | /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't |
806 | allow going from non-NULL pointer to NULL. */ | |
cb779afe AH |
807 | if (r.undefined_p () |
808 | || !r.contains_p (wi::zero (TYPE_PRECISION (TREE_TYPE (expr))))) | |
c39cb6bf JJ |
809 | { |
810 | /* We could here instead adjust r by off >> LOG2_BITS_PER_UNIT | |
811 | using POINTER_PLUS_EXPR if off_cst and just fall back to | |
812 | this. */ | |
45c8523d | 813 | r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt))); |
c39cb6bf JJ |
814 | return true; |
815 | } | |
4c85ff75 AM |
816 | } |
817 | /* If MEM_REF has a "positive" offset, consider it non-NULL | |
818 | always, for -fdelete-null-pointer-checks also "negative" | |
819 | ones. Punt for unknown offsets (e.g. variable ones). */ | |
820 | if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)) | |
821 | && off_cst | |
822 | && known_ne (off, 0) | |
823 | && (flag_delete_null_pointer_checks || known_gt (off, 0))) | |
824 | { | |
45c8523d | 825 | r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt))); |
4c85ff75 AM |
826 | return true; |
827 | } | |
45c8523d | 828 | r.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt))); |
4c85ff75 AM |
829 | return true; |
830 | } | |
831 | ||
832 | // Handle "= &a". | |
833 | if (tree_single_nonzero_warnv_p (expr, &strict_overflow_p)) | |
834 | { | |
45c8523d | 835 | r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt))); |
4c85ff75 AM |
836 | return true; |
837 | } | |
838 | ||
839 | // Otherwise return varying. | |
45c8523d | 840 | r.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt))); |
4c85ff75 AM |
841 | return true; |
842 | } | |
843 | ||
844 | // Calculate a range for phi statement S and return it in R. | |
845 | // If a range cannot be calculated, return false. | |
846 | ||
847 | bool | |
45c8523d | 848 | fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src) |
4c85ff75 AM |
849 | { |
850 | tree phi_def = gimple_phi_result (phi); | |
478cc962 | 851 | tree type = gimple_range_type (phi); |
45c8523d AH |
852 | Value_Range arg_range (type); |
853 | Value_Range equiv_range (type); | |
4c85ff75 AM |
854 | unsigned x; |
855 | ||
478cc962 | 856 | if (!type) |
4c85ff75 AM |
857 | return false; |
858 | ||
73cf73af AM |
859 | // Track if all executable arguments are the same. |
860 | tree single_arg = NULL_TREE; | |
861 | bool seen_arg = false; | |
862 | ||
4c85ff75 AM |
863 | // Start with an empty range, unioning in each argument's range. |
864 | r.set_undefined (); | |
865 | for (x = 0; x < gimple_phi_num_args (phi); x++) | |
866 | { | |
867 | tree arg = gimple_phi_arg_def (phi, x); | |
6d936684 AM |
868 | // An argument that is the same as the def provides no new range. |
869 | if (arg == phi_def) | |
870 | continue; | |
871 | ||
4c85ff75 AM |
872 | edge e = gimple_phi_arg_edge (phi, x); |
873 | ||
4c85ff75 AM |
874 | // Get the range of the argument on its edge. |
875 | src.get_phi_operand (arg_range, arg, e); | |
73cf73af AM |
876 | |
877 | if (!arg_range.undefined_p ()) | |
878 | { | |
879 | // Register potential dependencies for stale value tracking. | |
e43b15c8 AM |
880 | // Likewise, if the incoming PHI argument is equivalent to this |
881 | // PHI definition, it provides no new info. Accumulate these ranges | |
882 | // in case all arguments are equivalences. | |
ade5531c | 883 | if (src.query ()->query_relation (e, arg, phi_def, false) == VREL_EQ) |
e43b15c8 AM |
884 | equiv_range.union_(arg_range); |
885 | else | |
886 | r.union_ (arg_range); | |
887 | ||
73cf73af AM |
888 | if (gimple_range_ssa_p (arg) && src.gori ()) |
889 | src.gori ()->register_dependency (phi_def, arg); | |
17aa9ddb | 890 | } |
73cf73af | 891 | |
17aa9ddb AM |
892 | // Track if all arguments are the same. |
893 | if (!seen_arg) | |
894 | { | |
895 | seen_arg = true; | |
896 | single_arg = arg; | |
73cf73af | 897 | } |
17aa9ddb AM |
898 | else if (single_arg != arg) |
899 | single_arg = NULL_TREE; | |
73cf73af | 900 | |
4c85ff75 | 901 | // Once the value reaches varying, stop looking. |
73cf73af | 902 | if (r.varying_p () && single_arg == NULL_TREE) |
4c85ff75 AM |
903 | break; |
904 | } | |
905 | ||
c43bd879 AM |
906 | // If all arguments were equivalences, use the equivalence ranges as no |
907 | // arguments were processed. | |
908 | if (r.undefined_p () && !equiv_range.undefined_p ()) | |
909 | r = equiv_range; | |
910 | ||
911 | // If the PHI boils down to a single effective argument, look at it. | |
912 | if (single_arg) | |
913 | { | |
914 | // Symbolic arguments can be equivalences. | |
915 | if (gimple_range_ssa_p (single_arg)) | |
916 | { | |
917 | // Only allow the equivalence if the PHI definition does not | |
918 | // dominate any incoming edge for SINGLE_ARG. | |
919 | // See PR 108139 and 109462. | |
920 | basic_block bb = gimple_bb (phi); | |
921 | if (!dom_info_available_p (CDI_DOMINATORS)) | |
922 | single_arg = NULL; | |
923 | else | |
924 | for (x = 0; x < gimple_phi_num_args (phi); x++) | |
925 | if (gimple_phi_arg_def (phi, x) == single_arg | |
926 | && dominated_by_p (CDI_DOMINATORS, | |
927 | gimple_phi_arg_edge (phi, x)->src, | |
928 | bb)) | |
929 | { | |
930 | single_arg = NULL; | |
931 | break; | |
932 | } | |
933 | if (single_arg) | |
934 | src.register_relation (phi, VREL_EQ, phi_def, single_arg); | |
935 | } | |
936 | else if (src.get_operand (arg_range, single_arg) | |
937 | && arg_range.singleton_p ()) | |
938 | { | |
939 | // Numerical arguments that are a constant can be returned as | |
940 | // the constant. This can help fold later cases where even this | |
941 | // constant might have been UNDEFINED via an unreachable edge. | |
942 | r = arg_range; | |
943 | return true; | |
944 | } | |
945 | } | |
73cf73af | 946 | |
76a2d567 AM |
947 | // If PHI analysis is available, see if there is an iniital range. |
948 | if (phi_analysis_available_p () | |
949 | && irange::supports_p (TREE_TYPE (phi_def))) | |
950 | { | |
951 | phi_group *g = (phi_analysis())[phi_def]; | |
952 | if (g && !(g->range ().varying_p ())) | |
953 | { | |
954 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
955 | { | |
956 | fprintf (dump_file, "PHI GROUP query for "); | |
957 | print_generic_expr (dump_file, phi_def, TDF_SLIM); | |
958 | fprintf (dump_file, " found : "); | |
959 | g->range ().dump (dump_file); | |
960 | fprintf (dump_file, " and adjusted original range from :"); | |
961 | r.dump (dump_file); | |
962 | } | |
963 | r.intersect (g->range ()); | |
964 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
965 | { | |
966 | fprintf (dump_file, " to :"); | |
967 | r.dump (dump_file); | |
968 | fprintf (dump_file, "\n"); | |
969 | } | |
970 | } | |
971 | } | |
972 | ||
c46b5b0a | 973 | // If SCEV is available, query if this PHI has any known values. |
460dcec4 | 974 | if (scev_initialized_p () |
6d41f7c3 | 975 | && !POINTER_TYPE_P (TREE_TYPE (phi_def))) |
4c85ff75 | 976 | { |
4c85ff75 AM |
977 | class loop *l = loop_containing_stmt (phi); |
978 | if (l && loop_outer (l)) | |
979 | { | |
6d41f7c3 | 980 | Value_Range loop_range (type); |
4c85ff75 AM |
981 | range_of_ssa_name_with_loop_info (loop_range, phi_def, l, phi, src); |
982 | if (!loop_range.varying_p ()) | |
983 | { | |
984 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
985 | { | |
0cfc9c95 | 986 | fprintf (dump_file, "Loops range found for "); |
4c85ff75 AM |
987 | print_generic_expr (dump_file, phi_def, TDF_SLIM); |
988 | fprintf (dump_file, ": "); | |
989 | loop_range.dump (dump_file); | |
990 | fprintf (dump_file, " and calculated range :"); | |
991 | r.dump (dump_file); | |
992 | fprintf (dump_file, "\n"); | |
993 | } | |
994 | r.intersect (loop_range); | |
995 | } | |
996 | } | |
997 | } | |
998 | ||
999 | return true; | |
1000 | } | |
1001 | ||
1002 | // Calculate a range for call statement S and return it in R. | |
1003 | // If a range cannot be calculated, return false. | |
1004 | ||
1005 | bool | |
5608e410 | 1006 | fold_using_range::range_of_call (vrange &r, gcall *call, fur_source &) |
4c85ff75 | 1007 | { |
478cc962 AM |
1008 | tree type = gimple_range_type (call); |
1009 | if (!type) | |
1010 | return false; | |
1011 | ||
4c85ff75 AM |
1012 | tree lhs = gimple_call_lhs (call); |
1013 | bool strict_overflow_p; | |
1014 | ||
5608e410 | 1015 | if (gimple_stmt_nonnegative_warnv_p (call, &strict_overflow_p)) |
45c8523d | 1016 | r.set_nonnegative (type); |
4c85ff75 AM |
1017 | else if (gimple_call_nonnull_result_p (call) |
1018 | || gimple_call_nonnull_arg (call)) | |
45c8523d | 1019 | r.set_nonzero (type); |
4c85ff75 AM |
1020 | else |
1021 | r.set_varying (type); | |
1022 | ||
53ba8d66 JH |
1023 | tree callee = gimple_call_fndecl (call); |
1024 | if (callee | |
1025 | && useless_type_conversion_p (TREE_TYPE (TREE_TYPE (callee)), type)) | |
1026 | { | |
1027 | Value_Range val; | |
1028 | if (ipa_return_value_range (val, callee)) | |
1029 | { | |
1030 | r.intersect (val); | |
1031 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1032 | { | |
1033 | fprintf (dump_file, "Using return value range of "); | |
1034 | print_generic_expr (dump_file, callee, TDF_SLIM); | |
1035 | fprintf (dump_file, ": "); | |
1036 | val.dump (dump_file); | |
1037 | fprintf (dump_file, "\n"); | |
1038 | } | |
1039 | } | |
1040 | } | |
1041 | ||
4c85ff75 AM |
1042 | // If there is an LHS, intersect that with what is known. |
1043 | if (lhs) | |
1044 | { | |
45c8523d AH |
1045 | Value_Range def (TREE_TYPE (lhs)); |
1046 | gimple_range_global (def, lhs); | |
4c85ff75 AM |
1047 | r.intersect (def); |
1048 | } | |
1049 | return true; | |
1050 | } | |
1051 | ||
4c85ff75 AM |
1052 | // Calculate a range for COND_EXPR statement S and return it in R. |
1053 | // If a range cannot be calculated, return false. | |
1054 | ||
1055 | bool | |
45c8523d | 1056 | fold_using_range::range_of_cond_expr (vrange &r, gassign *s, fur_source &src) |
4c85ff75 | 1057 | { |
4c85ff75 AM |
1058 | tree cond = gimple_assign_rhs1 (s); |
1059 | tree op1 = gimple_assign_rhs2 (s); | |
1060 | tree op2 = gimple_assign_rhs3 (s); | |
1061 | ||
478cc962 AM |
1062 | tree type = gimple_range_type (s); |
1063 | if (!type) | |
4c85ff75 AM |
1064 | return false; |
1065 | ||
45c8523d AH |
1066 | Value_Range range1 (TREE_TYPE (op1)); |
1067 | Value_Range range2 (TREE_TYPE (op2)); | |
1068 | Value_Range cond_range (TREE_TYPE (cond)); | |
478cc962 AM |
1069 | gcc_checking_assert (gimple_assign_rhs_code (s) == COND_EXPR); |
1070 | gcc_checking_assert (range_compatible_p (TREE_TYPE (op1), TREE_TYPE (op2))); | |
4c85ff75 AM |
1071 | src.get_operand (cond_range, cond); |
1072 | src.get_operand (range1, op1); | |
1073 | src.get_operand (range2, op2); | |
1074 | ||
e15425e8 AM |
1075 | // Try to see if there is a dependence between the COND and either operand |
1076 | if (src.gori ()) | |
1077 | if (src.gori ()->condexpr_adjust (range1, range2, s, cond, op1, op2, src)) | |
1078 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1079 | { | |
1080 | fprintf (dump_file, "Possible COND_EXPR adjustment. Range op1 : "); | |
1081 | range1.dump(dump_file); | |
1082 | fprintf (dump_file, " and Range op2: "); | |
1083 | range2.dump(dump_file); | |
1084 | fprintf (dump_file, "\n"); | |
1085 | } | |
1086 | ||
4c85ff75 AM |
1087 | // If the condition is known, choose the appropriate expression. |
1088 | if (cond_range.singleton_p ()) | |
1089 | { | |
1090 | // False, pick second operand. | |
1091 | if (cond_range.zero_p ()) | |
1092 | r = range2; | |
1093 | else | |
1094 | r = range1; | |
1095 | } | |
1096 | else | |
1097 | { | |
1098 | r = range1; | |
1099 | r.union_ (range2); | |
1100 | } | |
ea789238 AM |
1101 | gcc_checking_assert (r.undefined_p () |
1102 | || range_compatible_p (r.type (), type)); | |
4c85ff75 AM |
1103 | return true; |
1104 | } | |
1105 | ||
1106 | // If SCEV has any information about phi node NAME, return it as a range in R. | |
1107 | ||
1108 | void | |
6d41f7c3 | 1109 | fold_using_range::range_of_ssa_name_with_loop_info (vrange &r, tree name, |
4c85ff75 AM |
1110 | class loop *l, gphi *phi, |
1111 | fur_source &src) | |
1112 | { | |
1113 | gcc_checking_assert (TREE_CODE (name) == SSA_NAME); | |
47a76439 AH |
1114 | if (!range_of_var_in_loop (r, name, l, phi, src.query ())) |
1115 | r.set_varying (TREE_TYPE (name)); | |
4c85ff75 AM |
1116 | } |
1117 | ||
1118 | // ----------------------------------------------------------------------- | |
1119 | ||
1120 | // Check if an && or || expression can be folded based on relations. ie | |
1121 | // c_2 = a_6 > b_7 | |
1122 | // c_3 = a_6 < b_7 | |
1123 | // c_4 = c_2 && c_3 | |
1124 | // c_2 and c_3 can never be true at the same time, | |
1125 | // Therefore c_4 can always resolve to false based purely on the relations. | |
1126 | ||
1127 | void | |
1128 | fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s, | |
9fedc3c0 AM |
1129 | fur_source &src, vrange &op1, |
1130 | vrange &op2) | |
4c85ff75 AM |
1131 | { |
1132 | // No queries or already folded. | |
1133 | if (!src.gori () || !src.query ()->oracle () || lhs_range.singleton_p ()) | |
1134 | return; | |
1135 | ||
1136 | // Only care about AND and OR expressions. | |
1137 | enum tree_code code = gimple_expr_code (s); | |
1138 | bool is_and = false; | |
1139 | if (code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) | |
1140 | is_and = true; | |
1141 | else if (code != BIT_IOR_EXPR && code != TRUTH_OR_EXPR) | |
1142 | return; | |
1143 | ||
51ce0638 AM |
1144 | gimple_range_op_handler handler (s); |
1145 | tree lhs = handler.lhs (); | |
1146 | tree ssa1 = gimple_range_ssa_p (handler.operand1 ()); | |
1147 | tree ssa2 = gimple_range_ssa_p (handler.operand2 ()); | |
4c85ff75 AM |
1148 | |
1149 | // Deal with || and && only when there is a full set of symbolics. | |
1150 | if (!lhs || !ssa1 || !ssa2 | |
1151 | || (TREE_CODE (TREE_TYPE (lhs)) != BOOLEAN_TYPE) | |
1152 | || (TREE_CODE (TREE_TYPE (ssa1)) != BOOLEAN_TYPE) | |
1153 | || (TREE_CODE (TREE_TYPE (ssa2)) != BOOLEAN_TYPE)) | |
1154 | return; | |
1155 | ||
1156 | // Now we know its a boolean AND or OR expression with boolean operands. | |
1157 | // Ideally we search dependencies for common names, and see what pops out. | |
1158 | // until then, simply try to resolve direct dependencies. | |
1159 | ||
918ccccb AM |
1160 | gimple *ssa1_stmt = SSA_NAME_DEF_STMT (ssa1); |
1161 | gimple *ssa2_stmt = SSA_NAME_DEF_STMT (ssa2); | |
1162 | ||
51ce0638 AM |
1163 | gimple_range_op_handler handler1 (ssa1_stmt); |
1164 | gimple_range_op_handler handler2 (ssa2_stmt); | |
918ccccb AM |
1165 | |
1166 | // If either handler is not present, no relation can be found. | |
1167 | if (!handler1 || !handler2) | |
1168 | return; | |
1169 | ||
1170 | // Both stmts will need to have 2 ssa names in the stmt. | |
51ce0638 AM |
1171 | tree ssa1_dep1 = gimple_range_ssa_p (handler1.operand1 ()); |
1172 | tree ssa1_dep2 = gimple_range_ssa_p (handler1.operand2 ()); | |
1173 | tree ssa2_dep1 = gimple_range_ssa_p (handler2.operand1 ()); | |
1174 | tree ssa2_dep2 = gimple_range_ssa_p (handler2.operand2 ()); | |
918ccccb AM |
1175 | |
1176 | if (!ssa1_dep1 || !ssa1_dep2 || !ssa2_dep1 || !ssa2_dep2) | |
4c85ff75 AM |
1177 | return; |
1178 | ||
ec5e99e9 AM |
1179 | if (HONOR_NANS (TREE_TYPE (ssa1_dep1))) |
1180 | return; | |
1181 | ||
4c85ff75 AM |
1182 | // Make sure they are the same dependencies, and detect the order of the |
1183 | // relationship. | |
1184 | bool reverse_op2 = true; | |
1185 | if (ssa1_dep1 == ssa2_dep1 && ssa1_dep2 == ssa2_dep2) | |
1186 | reverse_op2 = false; | |
1187 | else if (ssa1_dep1 != ssa2_dep2 || ssa1_dep2 != ssa2_dep1) | |
1188 | return; | |
1189 | ||
cb779afe | 1190 | int_range<2> bool_one = range_true (); |
9fedc3c0 AM |
1191 | relation_kind relation1 = handler1.op1_op2_relation (bool_one, op1, op2); |
1192 | relation_kind relation2 = handler2.op1_op2_relation (bool_one, op1, op2); | |
ade5531c | 1193 | if (relation1 == VREL_VARYING || relation2 == VREL_VARYING) |
4c85ff75 AM |
1194 | return; |
1195 | ||
1196 | if (reverse_op2) | |
1197 | relation2 = relation_negate (relation2); | |
1198 | ||
1199 | // x && y is false if the relation intersection of the true cases is NULL. | |
ade5531c | 1200 | if (is_and && relation_intersect (relation1, relation2) == VREL_UNDEFINED) |
cb779afe | 1201 | lhs_range = range_false (boolean_type_node); |
4c85ff75 | 1202 | // x || y is true if the union of the true cases is NO-RELATION.. |
c46b5b0a | 1203 | // ie, one or the other being true covers the full range of possibilities. |
ade5531c | 1204 | else if (!is_and && relation_union (relation1, relation2) == VREL_VARYING) |
4c85ff75 AM |
1205 | lhs_range = bool_one; |
1206 | else | |
1207 | return; | |
1208 | ||
1209 | range_cast (lhs_range, TREE_TYPE (lhs)); | |
1210 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1211 | { | |
1212 | fprintf (dump_file, " Relation adjustment: "); | |
1213 | print_generic_expr (dump_file, ssa1, TDF_SLIM); | |
1214 | fprintf (dump_file, " and "); | |
1215 | print_generic_expr (dump_file, ssa2, TDF_SLIM); | |
1216 | fprintf (dump_file, " combine to produce "); | |
1217 | lhs_range.dump (dump_file); | |
1218 | fputc ('\n', dump_file); | |
1219 | } | |
1220 | ||
1221 | return; | |
1222 | } | |
1223 | ||
1224 | // Register any outgoing edge relations from a conditional branch. | |
1225 | ||
1226 | void | |
9fedc3c0 AM |
1227 | fur_source::register_outgoing_edges (gcond *s, irange &lhs_range, |
1228 | edge e0, edge e1) | |
4c85ff75 | 1229 | { |
a0accaa9 | 1230 | int_range<2> e0_range, e1_range; |
4c85ff75 | 1231 | tree name; |
4c85ff75 AM |
1232 | basic_block bb = gimple_bb (s); |
1233 | ||
51ce0638 | 1234 | gimple_range_op_handler handler (s); |
70daecc0 AM |
1235 | if (!handler) |
1236 | return; | |
1237 | ||
198bc5ec | 1238 | if (e0) |
a0accaa9 AM |
1239 | { |
1240 | // If this edge is never taken, ignore it. | |
1241 | gcond_edge_range (e0_range, e0); | |
1242 | e0_range.intersect (lhs_range); | |
1243 | if (e0_range.undefined_p ()) | |
1244 | e0 = NULL; | |
1245 | } | |
1246 | ||
198bc5ec | 1247 | if (e1) |
a0accaa9 AM |
1248 | { |
1249 | // If this edge is never taken, ignore it. | |
1250 | gcond_edge_range (e1_range, e1); | |
1251 | e1_range.intersect (lhs_range); | |
1252 | if (e1_range.undefined_p ()) | |
1253 | e1 = NULL; | |
1254 | } | |
4c85ff75 | 1255 | |
4c85ff75 AM |
1256 | if (!e0 && !e1) |
1257 | return; | |
1258 | ||
1259 | // First, register the gcond itself. This will catch statements like | |
1260 | // if (a_2 < b_5) | |
51ce0638 AM |
1261 | tree ssa1 = gimple_range_ssa_p (handler.operand1 ()); |
1262 | tree ssa2 = gimple_range_ssa_p (handler.operand2 ()); | |
9fedc3c0 | 1263 | Value_Range r1,r2; |
4c85ff75 AM |
1264 | if (ssa1 && ssa2) |
1265 | { | |
9fedc3c0 AM |
1266 | r1.set_varying (TREE_TYPE (ssa1)); |
1267 | r2.set_varying (TREE_TYPE (ssa2)); | |
4c85ff75 AM |
1268 | if (e0) |
1269 | { | |
9fedc3c0 | 1270 | relation_kind relation = handler.op1_op2_relation (e0_range, r1, r2); |
ade5531c | 1271 | if (relation != VREL_VARYING) |
198bc5ec | 1272 | register_relation (e0, relation, ssa1, ssa2); |
4c85ff75 AM |
1273 | } |
1274 | if (e1) | |
1275 | { | |
9fedc3c0 | 1276 | relation_kind relation = handler.op1_op2_relation (e1_range, r1, r2); |
ade5531c | 1277 | if (relation != VREL_VARYING) |
198bc5ec | 1278 | register_relation (e1, relation, ssa1, ssa2); |
4c85ff75 AM |
1279 | } |
1280 | } | |
1281 | ||
1282 | // Outgoing relations of GORI exports require a gori engine. | |
198bc5ec | 1283 | if (!gori ()) |
4c85ff75 AM |
1284 | return; |
1285 | ||
4c85ff75 AM |
1286 | // Now look for other relations in the exports. This will find stmts |
1287 | // leading to the condition such as: | |
1288 | // c_2 = a_4 < b_7 | |
1289 | // if (c_2) | |
198bc5ec | 1290 | FOR_EACH_GORI_EXPORT_NAME (*(gori ()), bb, name) |
4c85ff75 AM |
1291 | { |
1292 | if (TREE_CODE (TREE_TYPE (name)) != BOOLEAN_TYPE) | |
1293 | continue; | |
1294 | gimple *stmt = SSA_NAME_DEF_STMT (name); | |
51ce0638 | 1295 | gimple_range_op_handler handler (stmt); |
4c85ff75 AM |
1296 | if (!handler) |
1297 | continue; | |
51ce0638 AM |
1298 | tree ssa1 = gimple_range_ssa_p (handler.operand1 ()); |
1299 | tree ssa2 = gimple_range_ssa_p (handler.operand2 ()); | |
45c8523d | 1300 | Value_Range r (TREE_TYPE (name)); |
4c85ff75 AM |
1301 | if (ssa1 && ssa2) |
1302 | { | |
9fedc3c0 AM |
1303 | r1.set_varying (TREE_TYPE (ssa1)); |
1304 | r2.set_varying (TREE_TYPE (ssa2)); | |
198bc5ec | 1305 | if (e0 && gori ()->outgoing_edge_range_p (r, e0, name, *m_query) |
4c85ff75 AM |
1306 | && r.singleton_p ()) |
1307 | { | |
9fedc3c0 | 1308 | relation_kind relation = handler.op1_op2_relation (r, r1, r2); |
ade5531c | 1309 | if (relation != VREL_VARYING) |
198bc5ec | 1310 | register_relation (e0, relation, ssa1, ssa2); |
4c85ff75 | 1311 | } |
198bc5ec | 1312 | if (e1 && gori ()->outgoing_edge_range_p (r, e1, name, *m_query) |
4c85ff75 AM |
1313 | && r.singleton_p ()) |
1314 | { | |
9fedc3c0 | 1315 | relation_kind relation = handler.op1_op2_relation (r, r1, r2); |
ade5531c | 1316 | if (relation != VREL_VARYING) |
198bc5ec | 1317 | register_relation (e1, relation, ssa1, ssa2); |
4c85ff75 AM |
1318 | } |
1319 | } | |
1320 | } | |
1321 | } |