]> gcc.gnu.org Git - gcc.git/blob - gcc/gimple-range-fold.cc
OpenACC: Fix reduction tree-sharing issue [PR106982]
[gcc.git] / gcc / gimple-range-fold.cc
1 /* Code for GIMPLE range related routines.
2 Copyright (C) 2019-2022 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@redhat.com>.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "backend.h"
26 #include "insn-codes.h"
27 #include "tree.h"
28 #include "gimple.h"
29 #include "ssa.h"
30 #include "gimple-pretty-print.h"
31 #include "optabs-tree.h"
32 #include "gimple-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"
40 #include "langhooks.h"
41 #include "vr-values.h"
42 #include "range.h"
43 #include "value-query.h"
44 #include "range-op.h"
45 #include "gimple-range.h"
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)
198 m_oracle->register_stmt (s, k, op1, op2);
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)
207 m_oracle->register_edge (e, k, op1, op2);
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[1] = 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);
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);
366 }
367 }
368
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 && gimple_assign_rhs_code (def_stmt) == COMPLEX_CST)
402 {
403 tree cst = gimple_assign_rhs1 (def_stmt);
404 if (TREE_CODE (cst) == COMPLEX_CST)
405 {
406 wide_int imag = wi::to_wide (TREE_IMAGPART (cst));
407 res.intersect (imag, imag);
408 }
409 }
410 }
411
412 // Adjust the range for a REALPART_EXPR.
413
414 static void
415 adjust_realpart_expr (irange &res, const gimple *stmt)
416 {
417 tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
418
419 if (TREE_CODE (name) != SSA_NAME)
420 return;
421
422 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
423 if (!SSA_NAME_DEF_STMT (name))
424 return;
425
426 if (is_gimple_assign (def_stmt)
427 && gimple_assign_rhs_code (def_stmt) == COMPLEX_CST)
428 {
429 tree cst = gimple_assign_rhs1 (def_stmt);
430 if (TREE_CODE (cst) == COMPLEX_CST)
431 {
432 tree imag = TREE_REALPART (cst);
433 int_range<2> tmp (imag, imag);
434 res.intersect (tmp);
435 }
436 }
437 }
438
439 // This function looks for situations when walking the use/def chains
440 // may provide additonal contextual range information not exposed on
441 // this statement.
442
443 static void
444 gimple_range_adjustment (irange &res, const gimple *stmt)
445 {
446 switch (gimple_expr_code (stmt))
447 {
448 case POINTER_DIFF_EXPR:
449 adjust_pointer_diff_expr (res, stmt);
450 return;
451
452 case IMAGPART_EXPR:
453 adjust_imagpart_expr (res, stmt);
454 return;
455
456 case REALPART_EXPR:
457 adjust_realpart_expr (res, stmt);
458 return;
459
460 default:
461 break;
462 }
463 }
464
465 // Return the base of the RHS of an assignment.
466
467 static tree
468 gimple_range_base_of_assignment (const gimple *stmt)
469 {
470 gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN);
471 tree op1 = gimple_assign_rhs1 (stmt);
472 if (gimple_assign_rhs_code (stmt) == ADDR_EXPR)
473 return get_base_address (TREE_OPERAND (op1, 0));
474 return op1;
475 }
476
477 // Return the first operand of this statement if it is a valid operand
478 // supported by ranges, otherwise return NULL_TREE. Special case is
479 // &(SSA_NAME expr), return the SSA_NAME instead of the ADDR expr.
480
481 tree
482 gimple_range_operand1 (const gimple *stmt)
483 {
484 gcc_checking_assert (gimple_range_handler (stmt));
485
486 switch (gimple_code (stmt))
487 {
488 case GIMPLE_COND:
489 return gimple_cond_lhs (stmt);
490 case GIMPLE_ASSIGN:
491 {
492 tree base = gimple_range_base_of_assignment (stmt);
493 if (base && TREE_CODE (base) == MEM_REF)
494 {
495 // If the base address is an SSA_NAME, we return it
496 // here. This allows processing of the range of that
497 // name, while the rest of the expression is simply
498 // ignored. The code in range_ops will see the
499 // ADDR_EXPR and do the right thing.
500 tree ssa = TREE_OPERAND (base, 0);
501 if (TREE_CODE (ssa) == SSA_NAME)
502 return ssa;
503 }
504 return base;
505 }
506 default:
507 break;
508 }
509 return NULL;
510 }
511
512 // Return the second operand of statement STMT, otherwise return NULL_TREE.
513
514 tree
515 gimple_range_operand2 (const gimple *stmt)
516 {
517 gcc_checking_assert (gimple_range_handler (stmt));
518
519 switch (gimple_code (stmt))
520 {
521 case GIMPLE_COND:
522 return gimple_cond_rhs (stmt);
523 case GIMPLE_ASSIGN:
524 if (gimple_num_ops (stmt) >= 3)
525 return gimple_assign_rhs2 (stmt);
526 default:
527 break;
528 }
529 return NULL_TREE;
530 }
531
532 // Calculate a range for statement S and return it in R. If NAME is provided it
533 // represents the SSA_NAME on the LHS of the statement. It is only required
534 // if there is more than one lhs/output. If a range cannot
535 // be calculated, return false.
536
537 bool
538 fold_using_range::fold_stmt (irange &r, gimple *s, fur_source &src, tree name)
539 {
540 bool res = false;
541 // If name and S are specified, make sure it is an LHS of S.
542 gcc_checking_assert (!name || !gimple_get_lhs (s) ||
543 name == gimple_get_lhs (s));
544
545 if (!name)
546 name = gimple_get_lhs (s);
547
548 // Process addresses.
549 if (gimple_code (s) == GIMPLE_ASSIGN
550 && gimple_assign_rhs_code (s) == ADDR_EXPR)
551 return range_of_address (r, s, src);
552
553 if (gimple_range_handler (s))
554 res = range_of_range_op (r, s, src);
555 else if (is_a<gphi *>(s))
556 res = range_of_phi (r, as_a<gphi *> (s), src);
557 else if (is_a<gcall *>(s))
558 res = range_of_call (r, as_a<gcall *> (s), src);
559 else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR)
560 res = range_of_cond_expr (r, as_a<gassign *> (s), src);
561
562 if (!res)
563 {
564 // If no name specified or range is unsupported, bail.
565 if (!name || !gimple_range_ssa_p (name))
566 return false;
567 // We don't understand the stmt, so return the global range.
568 r = gimple_range_global (name);
569 return true;
570 }
571
572 if (r.undefined_p ())
573 return true;
574
575 // We sometimes get compatible types copied from operands, make sure
576 // the correct type is being returned.
577 if (name && TREE_TYPE (name) != r.type ())
578 {
579 gcc_checking_assert (range_compatible_p (r.type (), TREE_TYPE (name)));
580 range_cast (r, TREE_TYPE (name));
581 }
582 return true;
583 }
584
585 // Calculate a range for range_op statement S and return it in R. If any
586 // If a range cannot be calculated, return false.
587
588 bool
589 fold_using_range::range_of_range_op (irange &r, gimple *s, fur_source &src)
590 {
591 int_range_max range1, range2;
592 tree type = gimple_range_type (s);
593 if (!type)
594 return false;
595 range_operator *handler = gimple_range_handler (s);
596 gcc_checking_assert (handler);
597
598 tree lhs = gimple_get_lhs (s);
599 tree op1 = gimple_range_operand1 (s);
600 tree op2 = gimple_range_operand2 (s);
601
602 if (src.get_operand (range1, op1))
603 {
604 if (!op2)
605 {
606 // Fold range, and register any dependency if available.
607 int_range<2> r2 (type);
608 handler->fold_range (r, type, range1, r2);
609 if (lhs && gimple_range_ssa_p (op1))
610 {
611 if (src.gori ())
612 src.gori ()->register_dependency (lhs, op1);
613 relation_kind rel;
614 rel = handler->lhs_op1_relation (r, range1, range1);
615 if (rel != VREL_NONE)
616 src.register_relation (s, rel, lhs, op1);
617 }
618 }
619 else if (src.get_operand (range2, op2))
620 {
621 relation_kind rel = src.query_relation (op1, op2);
622 if (dump_file && (dump_flags & TDF_DETAILS) && rel != VREL_NONE)
623 {
624 fprintf (dump_file, " folding with relation ");
625 print_generic_expr (dump_file, op1, TDF_SLIM);
626 print_relation (dump_file, rel);
627 print_generic_expr (dump_file, op2, TDF_SLIM);
628 fputc ('\n', dump_file);
629 }
630 // Fold range, and register any dependency if available.
631 handler->fold_range (r, type, range1, range2, rel);
632 relation_fold_and_or (r, s, src);
633 if (lhs)
634 {
635 if (src.gori ())
636 {
637 src.gori ()->register_dependency (lhs, op1);
638 src.gori ()->register_dependency (lhs, op2);
639 }
640 if (gimple_range_ssa_p (op1))
641 {
642 rel = handler->lhs_op1_relation (r, range1, range2);
643 if (rel != VREL_NONE)
644 src.register_relation (s, rel, lhs, op1);
645 }
646 if (gimple_range_ssa_p (op2))
647 {
648 rel= handler->lhs_op2_relation (r, range1, range2);
649 if (rel != VREL_NONE)
650 src.register_relation (s, rel, lhs, op2);
651 }
652 }
653 // Check for an existing BB, as we maybe asked to fold an
654 // artificial statement not in the CFG.
655 else if (is_a<gcond *> (s) && gimple_bb (s))
656 {
657 basic_block bb = gimple_bb (s);
658 edge e0 = EDGE_SUCC (bb, 0);
659 edge e1 = EDGE_SUCC (bb, 1);
660
661 if (!single_pred_p (e0->dest))
662 e0 = NULL;
663 if (!single_pred_p (e1->dest))
664 e1 = NULL;
665 src.register_outgoing_edges (as_a<gcond *> (s), r, e0, e1);
666 }
667 }
668 else
669 r.set_varying (type);
670 }
671 else
672 r.set_varying (type);
673 // Make certain range-op adjustments that aren't handled any other way.
674 gimple_range_adjustment (r, s);
675 return true;
676 }
677
678 // Calculate the range of an assignment containing an ADDR_EXPR.
679 // Return the range in R.
680 // If a range cannot be calculated, set it to VARYING and return true.
681
682 bool
683 fold_using_range::range_of_address (irange &r, gimple *stmt, fur_source &src)
684 {
685 gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN);
686 gcc_checking_assert (gimple_assign_rhs_code (stmt) == ADDR_EXPR);
687
688 bool strict_overflow_p;
689 tree expr = gimple_assign_rhs1 (stmt);
690 poly_int64 bitsize, bitpos;
691 tree offset;
692 machine_mode mode;
693 int unsignedp, reversep, volatilep;
694 tree base = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize,
695 &bitpos, &offset, &mode, &unsignedp,
696 &reversep, &volatilep);
697
698
699 if (base != NULL_TREE
700 && TREE_CODE (base) == MEM_REF
701 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
702 {
703 tree ssa = TREE_OPERAND (base, 0);
704 tree lhs = gimple_get_lhs (stmt);
705 if (lhs && gimple_range_ssa_p (ssa) && src.gori ())
706 src.gori ()->register_dependency (lhs, ssa);
707 gcc_checking_assert (irange::supports_type_p (TREE_TYPE (ssa)));
708 src.get_operand (r, ssa);
709 range_cast (r, TREE_TYPE (gimple_assign_rhs1 (stmt)));
710
711 poly_offset_int off = 0;
712 bool off_cst = false;
713 if (offset == NULL_TREE || TREE_CODE (offset) == INTEGER_CST)
714 {
715 off = mem_ref_offset (base);
716 if (offset)
717 off += poly_offset_int::from (wi::to_poly_wide (offset),
718 SIGNED);
719 off <<= LOG2_BITS_PER_UNIT;
720 off += bitpos;
721 off_cst = true;
722 }
723 /* If &X->a is equal to X, the range of X is the result. */
724 if (off_cst && known_eq (off, 0))
725 return true;
726 else if (flag_delete_null_pointer_checks
727 && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)))
728 {
729 /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
730 allow going from non-NULL pointer to NULL. */
731 if (!range_includes_zero_p (&r))
732 {
733 /* We could here instead adjust r by off >> LOG2_BITS_PER_UNIT
734 using POINTER_PLUS_EXPR if off_cst and just fall back to
735 this. */
736 r = range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
737 return true;
738 }
739 }
740 /* If MEM_REF has a "positive" offset, consider it non-NULL
741 always, for -fdelete-null-pointer-checks also "negative"
742 ones. Punt for unknown offsets (e.g. variable ones). */
743 if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))
744 && off_cst
745 && known_ne (off, 0)
746 && (flag_delete_null_pointer_checks || known_gt (off, 0)))
747 {
748 r = range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
749 return true;
750 }
751 r = int_range<2> (TREE_TYPE (gimple_assign_rhs1 (stmt)));
752 return true;
753 }
754
755 // Handle "= &a".
756 if (tree_single_nonzero_warnv_p (expr, &strict_overflow_p))
757 {
758 r = range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
759 return true;
760 }
761
762 // Otherwise return varying.
763 r = int_range<2> (TREE_TYPE (gimple_assign_rhs1 (stmt)));
764 return true;
765 }
766
767 // Calculate a range for phi statement S and return it in R.
768 // If a range cannot be calculated, return false.
769
770 bool
771 fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src)
772 {
773 tree phi_def = gimple_phi_result (phi);
774 tree type = gimple_range_type (phi);
775 int_range_max arg_range;
776 int_range_max equiv_range;
777 unsigned x;
778
779 if (!type)
780 return false;
781
782 // Track if all executable arguments are the same.
783 tree single_arg = NULL_TREE;
784 bool seen_arg = false;
785
786 // Start with an empty range, unioning in each argument's range.
787 r.set_undefined ();
788 for (x = 0; x < gimple_phi_num_args (phi); x++)
789 {
790 tree arg = gimple_phi_arg_def (phi, x);
791 // An argument that is the same as the def provides no new range.
792 if (arg == phi_def)
793 continue;
794
795 edge e = gimple_phi_arg_edge (phi, x);
796
797 // Get the range of the argument on its edge.
798 src.get_phi_operand (arg_range, arg, e);
799
800 if (!arg_range.undefined_p ())
801 {
802 // Register potential dependencies for stale value tracking.
803 // Likewise, if the incoming PHI argument is equivalent to this
804 // PHI definition, it provides no new info. Accumulate these ranges
805 // in case all arguments are equivalences.
806 if (src.query ()->query_relation (e, arg, phi_def, false) == EQ_EXPR)
807 equiv_range.union_(arg_range);
808 else
809 r.union_ (arg_range);
810
811 if (gimple_range_ssa_p (arg) && src.gori ())
812 src.gori ()->register_dependency (phi_def, arg);
813
814 // Track if all arguments are the same.
815 if (!seen_arg)
816 {
817 seen_arg = true;
818 single_arg = arg;
819 }
820 else if (single_arg != arg)
821 single_arg = NULL_TREE;
822 }
823
824 // Once the value reaches varying, stop looking.
825 if (r.varying_p () && single_arg == NULL_TREE)
826 break;
827 }
828
829 // If all arguments were equivalences, use the equivalence ranges as no
830 // arguments were processed.
831 if (r.undefined_p () && !equiv_range.undefined_p ())
832 r = equiv_range;
833
834 // If the PHI boils down to a single effective argument, look at it.
835 if (single_arg)
836 {
837 // Symbolic arguments are equivalences.
838 if (gimple_range_ssa_p (single_arg))
839 src.register_relation (phi, EQ_EXPR, phi_def, single_arg);
840 else if (src.get_operand (arg_range, single_arg)
841 && arg_range.singleton_p ())
842 {
843 // Numerical arguments that are a constant can be returned as
844 // the constant. This can help fold later cases where even this
845 // constant might have been UNDEFINED via an unreachable edge.
846 r = arg_range;
847 return true;
848 }
849 }
850
851 // If SCEV is available, query if this PHI has any knonwn values.
852 if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
853 {
854 value_range loop_range;
855 class loop *l = loop_containing_stmt (phi);
856 if (l && loop_outer (l))
857 {
858 range_of_ssa_name_with_loop_info (loop_range, phi_def, l, phi, src);
859 if (!loop_range.varying_p ())
860 {
861 if (dump_file && (dump_flags & TDF_DETAILS))
862 {
863 fprintf (dump_file, " Loops range found for ");
864 print_generic_expr (dump_file, phi_def, TDF_SLIM);
865 fprintf (dump_file, ": ");
866 loop_range.dump (dump_file);
867 fprintf (dump_file, " and calculated range :");
868 r.dump (dump_file);
869 fprintf (dump_file, "\n");
870 }
871 r.intersect (loop_range);
872 }
873 }
874 }
875
876 return true;
877 }
878
879 // Calculate a range for call statement S and return it in R.
880 // If a range cannot be calculated, return false.
881
882 bool
883 fold_using_range::range_of_call (irange &r, gcall *call, fur_source &src)
884 {
885 tree type = gimple_range_type (call);
886 if (!type)
887 return false;
888
889 tree lhs = gimple_call_lhs (call);
890 bool strict_overflow_p;
891
892 if (range_of_builtin_call (r, call, src))
893 ;
894 else if (gimple_stmt_nonnegative_warnv_p (call, &strict_overflow_p))
895 r.set (build_int_cst (type, 0), TYPE_MAX_VALUE (type));
896 else if (gimple_call_nonnull_result_p (call)
897 || gimple_call_nonnull_arg (call))
898 r = range_nonzero (type);
899 else
900 r.set_varying (type);
901
902 // If there is an LHS, intersect that with what is known.
903 if (lhs)
904 {
905 value_range def;
906 def = gimple_range_global (lhs);
907 r.intersect (def);
908 }
909 return true;
910 }
911
912 // Return the range of a __builtin_ubsan* in CALL and set it in R.
913 // CODE is the type of ubsan call (PLUS_EXPR, MINUS_EXPR or
914 // MULT_EXPR).
915
916 void
917 fold_using_range::range_of_builtin_ubsan_call (irange &r, gcall *call,
918 tree_code code, fur_source &src)
919 {
920 gcc_checking_assert (code == PLUS_EXPR || code == MINUS_EXPR
921 || code == MULT_EXPR);
922 tree type = gimple_range_type (call);
923 range_operator *op = range_op_handler (code, type);
924 gcc_checking_assert (op);
925 int_range_max ir0, ir1;
926 tree arg0 = gimple_call_arg (call, 0);
927 tree arg1 = gimple_call_arg (call, 1);
928 src.get_operand (ir0, arg0);
929 src.get_operand (ir1, arg1);
930 // Check for any relation between arg0 and arg1.
931 relation_kind relation = src.query_relation (arg0, arg1);
932
933 bool saved_flag_wrapv = flag_wrapv;
934 // Pretend the arithmetic is wrapping. If there is any overflow,
935 // we'll complain, but will actually do wrapping operation.
936 flag_wrapv = 1;
937 op->fold_range (r, type, ir0, ir1, relation);
938 flag_wrapv = saved_flag_wrapv;
939
940 // If for both arguments vrp_valueize returned non-NULL, this should
941 // have been already folded and if not, it wasn't folded because of
942 // overflow. Avoid removing the UBSAN_CHECK_* calls in that case.
943 if (r.singleton_p ())
944 r.set_varying (type);
945 }
946
947 // Return TRUE if we recognize the target character set and return the
948 // range for lower case and upper case letters.
949
950 static bool
951 get_letter_range (tree type, irange &lowers, irange &uppers)
952 {
953 // ASCII
954 int a = lang_hooks.to_target_charset ('a');
955 int z = lang_hooks.to_target_charset ('z');
956 int A = lang_hooks.to_target_charset ('A');
957 int Z = lang_hooks.to_target_charset ('Z');
958
959 if ((z - a == 25) && (Z - A == 25))
960 {
961 lowers = int_range<2> (build_int_cst (type, a), build_int_cst (type, z));
962 uppers = int_range<2> (build_int_cst (type, A), build_int_cst (type, Z));
963 return true;
964 }
965 // Unknown character set.
966 return false;
967 }
968
969 // For a builtin in CALL, return a range in R if known and return
970 // TRUE. Otherwise return FALSE.
971
972 bool
973 fold_using_range::range_of_builtin_call (irange &r, gcall *call,
974 fur_source &src)
975 {
976 combined_fn func = gimple_call_combined_fn (call);
977 if (func == CFN_LAST)
978 return false;
979
980 tree type = gimple_range_type (call);
981 tree arg;
982 int mini, maxi, zerov = 0, prec;
983 scalar_int_mode mode;
984
985 switch (func)
986 {
987 case CFN_BUILT_IN_CONSTANT_P:
988 arg = gimple_call_arg (call, 0);
989 if (src.get_operand (r, arg) && r.singleton_p ())
990 {
991 r.set (build_one_cst (type), build_one_cst (type));
992 return true;
993 }
994 if (cfun->after_inlining)
995 {
996 r.set_zero (type);
997 // r.equiv_clear ();
998 return true;
999 }
1000 break;
1001
1002 case CFN_BUILT_IN_TOUPPER:
1003 {
1004 arg = gimple_call_arg (call, 0);
1005 // If the argument isn't compatible with the LHS, do nothing.
1006 if (!range_compatible_p (type, TREE_TYPE (arg)))
1007 return false;
1008 if (!src.get_operand (r, arg))
1009 return false;
1010
1011 int_range<3> lowers;
1012 int_range<3> uppers;
1013 if (!get_letter_range (type, lowers, uppers))
1014 return false;
1015
1016 // Return the range passed in without any lower case characters,
1017 // but including all the upper case ones.
1018 lowers.invert ();
1019 r.intersect (lowers);
1020 r.union_ (uppers);
1021 return true;
1022 }
1023
1024 case CFN_BUILT_IN_TOLOWER:
1025 {
1026 arg = gimple_call_arg (call, 0);
1027 // If the argument isn't compatible with the LHS, do nothing.
1028 if (!range_compatible_p (type, TREE_TYPE (arg)))
1029 return false;
1030 if (!src.get_operand (r, arg))
1031 return false;
1032
1033 int_range<3> lowers;
1034 int_range<3> uppers;
1035 if (!get_letter_range (type, lowers, uppers))
1036 return false;
1037
1038 // Return the range passed in without any upper case characters,
1039 // but including all the lower case ones.
1040 uppers.invert ();
1041 r.intersect (uppers);
1042 r.union_ (lowers);
1043 return true;
1044 }
1045
1046 CASE_CFN_FFS:
1047 CASE_CFN_POPCOUNT:
1048 // __builtin_ffs* and __builtin_popcount* return [0, prec].
1049 arg = gimple_call_arg (call, 0);
1050 prec = TYPE_PRECISION (TREE_TYPE (arg));
1051 mini = 0;
1052 maxi = prec;
1053 src.get_operand (r, arg);
1054 // If arg is non-zero, then ffs or popcount are non-zero.
1055 if (!range_includes_zero_p (&r))
1056 mini = 1;
1057 // If some high bits are known to be zero, decrease the maximum.
1058 if (!r.undefined_p ())
1059 {
1060 if (TYPE_SIGN (r.type ()) == SIGNED)
1061 range_cast (r, unsigned_type_for (r.type ()));
1062 wide_int max = r.upper_bound ();
1063 maxi = wi::floor_log2 (max) + 1;
1064 }
1065 r.set (build_int_cst (type, mini), build_int_cst (type, maxi));
1066 return true;
1067
1068 CASE_CFN_PARITY:
1069 r.set (build_zero_cst (type), build_one_cst (type));
1070 return true;
1071
1072 CASE_CFN_CLZ:
1073 // __builtin_c[lt]z* return [0, prec-1], except when the
1074 // argument is 0, but that is undefined behavior.
1075 //
1076 // For __builtin_c[lt]z* consider argument of 0 always undefined
1077 // behavior, for internal fns depending on C?Z_DEFINED_VALUE_AT_ZERO.
1078 arg = gimple_call_arg (call, 0);
1079 prec = TYPE_PRECISION (TREE_TYPE (arg));
1080 mini = 0;
1081 maxi = prec - 1;
1082 mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
1083 if (gimple_call_internal_p (call))
1084 {
1085 if (optab_handler (clz_optab, mode) != CODE_FOR_nothing
1086 && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov) == 2)
1087 {
1088 // Only handle the single common value.
1089 if (zerov == prec)
1090 maxi = prec;
1091 else
1092 // Magic value to give up, unless we can prove arg is non-zero.
1093 mini = -2;
1094 }
1095 }
1096
1097 src.get_operand (r, arg);
1098 // From clz of minimum we can compute result maximum.
1099 if (!r.undefined_p ())
1100 {
1101 // From clz of minimum we can compute result maximum.
1102 if (wi::gt_p (r.lower_bound (), 0, TYPE_SIGN (r.type ())))
1103 {
1104 maxi = prec - 1 - wi::floor_log2 (r.lower_bound ());
1105 if (mini == -2)
1106 mini = 0;
1107 }
1108 else if (!range_includes_zero_p (&r))
1109 {
1110 mini = 0;
1111 maxi = prec - 1;
1112 }
1113 if (mini == -2)
1114 break;
1115 // From clz of maximum we can compute result minimum.
1116 wide_int max = r.upper_bound ();
1117 int newmini = prec - 1 - wi::floor_log2 (max);
1118 if (max == 0)
1119 {
1120 // If CLZ_DEFINED_VALUE_AT_ZERO is 2 with VALUE of prec,
1121 // return [prec, prec], otherwise ignore the range.
1122 if (maxi == prec)
1123 mini = prec;
1124 }
1125 else
1126 mini = newmini;
1127 }
1128 if (mini == -2)
1129 break;
1130 r.set (build_int_cst (type, mini), build_int_cst (type, maxi));
1131 return true;
1132
1133 CASE_CFN_CTZ:
1134 // __builtin_ctz* return [0, prec-1], except for when the
1135 // argument is 0, but that is undefined behavior.
1136 //
1137 // For __builtin_ctz* consider argument of 0 always undefined
1138 // behavior, for internal fns depending on CTZ_DEFINED_VALUE_AT_ZERO.
1139 arg = gimple_call_arg (call, 0);
1140 prec = TYPE_PRECISION (TREE_TYPE (arg));
1141 mini = 0;
1142 maxi = prec - 1;
1143 mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
1144 if (gimple_call_internal_p (call))
1145 {
1146 if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing
1147 && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov) == 2)
1148 {
1149 // Handle only the two common values.
1150 if (zerov == -1)
1151 mini = -1;
1152 else if (zerov == prec)
1153 maxi = prec;
1154 else
1155 // Magic value to give up, unless we can prove arg is non-zero.
1156 mini = -2;
1157 }
1158 }
1159 src.get_operand (r, arg);
1160 if (!r.undefined_p ())
1161 {
1162 // If arg is non-zero, then use [0, prec - 1].
1163 if (!range_includes_zero_p (&r))
1164 {
1165 mini = 0;
1166 maxi = prec - 1;
1167 }
1168 // If some high bits are known to be zero, we can decrease
1169 // the maximum.
1170 wide_int max = r.upper_bound ();
1171 if (max == 0)
1172 {
1173 // Argument is [0, 0]. If CTZ_DEFINED_VALUE_AT_ZERO
1174 // is 2 with value -1 or prec, return [-1, -1] or [prec, prec].
1175 // Otherwise ignore the range.
1176 if (mini == -1)
1177 maxi = -1;
1178 else if (maxi == prec)
1179 mini = prec;
1180 }
1181 // If value at zero is prec and 0 is in the range, we can't lower
1182 // the upper bound. We could create two separate ranges though,
1183 // [0,floor_log2(max)][prec,prec] though.
1184 else if (maxi != prec)
1185 maxi = wi::floor_log2 (max);
1186 }
1187 if (mini == -2)
1188 break;
1189 r.set (build_int_cst (type, mini), build_int_cst (type, maxi));
1190 return true;
1191
1192 CASE_CFN_CLRSB:
1193 arg = gimple_call_arg (call, 0);
1194 prec = TYPE_PRECISION (TREE_TYPE (arg));
1195 r.set (build_int_cst (type, 0), build_int_cst (type, prec - 1));
1196 return true;
1197 case CFN_UBSAN_CHECK_ADD:
1198 range_of_builtin_ubsan_call (r, call, PLUS_EXPR, src);
1199 return true;
1200 case CFN_UBSAN_CHECK_SUB:
1201 range_of_builtin_ubsan_call (r, call, MINUS_EXPR, src);
1202 return true;
1203 case CFN_UBSAN_CHECK_MUL:
1204 range_of_builtin_ubsan_call (r, call, MULT_EXPR, src);
1205 return true;
1206
1207 case CFN_GOACC_DIM_SIZE:
1208 case CFN_GOACC_DIM_POS:
1209 // Optimizing these two internal functions helps the loop
1210 // optimizer eliminate outer comparisons. Size is [1,N]
1211 // and pos is [0,N-1].
1212 {
1213 bool is_pos = func == CFN_GOACC_DIM_POS;
1214 int axis = oacc_get_ifn_dim_arg (call);
1215 int size = oacc_get_fn_dim_size (current_function_decl, axis);
1216 if (!size)
1217 // If it's dynamic, the backend might know a hardware limitation.
1218 size = targetm.goacc.dim_limit (axis);
1219
1220 r.set (build_int_cst (type, is_pos ? 0 : 1),
1221 size
1222 ? build_int_cst (type, size - is_pos) : vrp_val_max (type));
1223 return true;
1224 }
1225
1226 case CFN_BUILT_IN_STRLEN:
1227 if (tree lhs = gimple_call_lhs (call))
1228 if (ptrdiff_type_node
1229 && (TYPE_PRECISION (ptrdiff_type_node)
1230 == TYPE_PRECISION (TREE_TYPE (lhs))))
1231 {
1232 tree type = TREE_TYPE (lhs);
1233 tree max = vrp_val_max (ptrdiff_type_node);
1234 wide_int wmax
1235 = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
1236 tree range_min = build_zero_cst (type);
1237 // To account for the terminating NULL, the maximum length
1238 // is one less than the maximum array size, which in turn
1239 // is one less than PTRDIFF_MAX (or SIZE_MAX where it's
1240 // smaller than the former type).
1241 // FIXME: Use max_object_size() - 1 here.
1242 tree range_max = wide_int_to_tree (type, wmax - 2);
1243 r.set (range_min, range_max);
1244 return true;
1245 }
1246 break;
1247 default:
1248 break;
1249 }
1250 return false;
1251 }
1252
1253
1254 // Calculate a range for COND_EXPR statement S and return it in R.
1255 // If a range cannot be calculated, return false.
1256
1257 bool
1258 fold_using_range::range_of_cond_expr (irange &r, gassign *s, fur_source &src)
1259 {
1260 int_range_max cond_range, range1, range2;
1261 tree cond = gimple_assign_rhs1 (s);
1262 tree op1 = gimple_assign_rhs2 (s);
1263 tree op2 = gimple_assign_rhs3 (s);
1264
1265 tree type = gimple_range_type (s);
1266 if (!type)
1267 return false;
1268
1269 gcc_checking_assert (gimple_assign_rhs_code (s) == COND_EXPR);
1270 gcc_checking_assert (range_compatible_p (TREE_TYPE (op1), TREE_TYPE (op2)));
1271 src.get_operand (cond_range, cond);
1272 src.get_operand (range1, op1);
1273 src.get_operand (range2, op2);
1274
1275 // Try to see if there is a dependence between the COND and either operand
1276 if (src.gori ())
1277 if (src.gori ()->condexpr_adjust (range1, range2, s, cond, op1, op2, src))
1278 if (dump_file && (dump_flags & TDF_DETAILS))
1279 {
1280 fprintf (dump_file, "Possible COND_EXPR adjustment. Range op1 : ");
1281 range1.dump(dump_file);
1282 fprintf (dump_file, " and Range op2: ");
1283 range2.dump(dump_file);
1284 fprintf (dump_file, "\n");
1285 }
1286
1287 // If the condition is known, choose the appropriate expression.
1288 if (cond_range.singleton_p ())
1289 {
1290 // False, pick second operand.
1291 if (cond_range.zero_p ())
1292 r = range2;
1293 else
1294 r = range1;
1295 }
1296 else
1297 {
1298 r = range1;
1299 r.union_ (range2);
1300 }
1301 gcc_checking_assert (r.undefined_p ()
1302 || range_compatible_p (r.type (), type));
1303 return true;
1304 }
1305
1306 // If SCEV has any information about phi node NAME, return it as a range in R.
1307
1308 void
1309 fold_using_range::range_of_ssa_name_with_loop_info (irange &r, tree name,
1310 class loop *l, gphi *phi,
1311 fur_source &src)
1312 {
1313 gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
1314 tree min, max, type = TREE_TYPE (name);
1315 if (bounds_of_var_in_loop (&min, &max, src.query (), l, phi, name))
1316 {
1317 if (TREE_CODE (min) != INTEGER_CST)
1318 {
1319 if (src.query ()->range_of_expr (r, min, phi) && !r.undefined_p ())
1320 min = wide_int_to_tree (type, r.lower_bound ());
1321 else
1322 min = vrp_val_min (type);
1323 }
1324 if (TREE_CODE (max) != INTEGER_CST)
1325 {
1326 if (src.query ()->range_of_expr (r, max, phi) && !r.undefined_p ())
1327 max = wide_int_to_tree (type, r.upper_bound ());
1328 else
1329 max = vrp_val_max (type);
1330 }
1331 r.set (min, max);
1332 }
1333 else
1334 r.set_varying (type);
1335 }
1336
1337 // -----------------------------------------------------------------------
1338
1339 // Check if an && or || expression can be folded based on relations. ie
1340 // c_2 = a_6 > b_7
1341 // c_3 = a_6 < b_7
1342 // c_4 = c_2 && c_3
1343 // c_2 and c_3 can never be true at the same time,
1344 // Therefore c_4 can always resolve to false based purely on the relations.
1345
1346 void
1347 fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s,
1348 fur_source &src)
1349 {
1350 // No queries or already folded.
1351 if (!src.gori () || !src.query ()->oracle () || lhs_range.singleton_p ())
1352 return;
1353
1354 // Only care about AND and OR expressions.
1355 enum tree_code code = gimple_expr_code (s);
1356 bool is_and = false;
1357 if (code == BIT_AND_EXPR || code == TRUTH_AND_EXPR)
1358 is_and = true;
1359 else if (code != BIT_IOR_EXPR && code != TRUTH_OR_EXPR)
1360 return;
1361
1362 tree lhs = gimple_get_lhs (s);
1363 tree ssa1 = gimple_range_ssa_p (gimple_range_operand1 (s));
1364 tree ssa2 = gimple_range_ssa_p (gimple_range_operand2 (s));
1365
1366 // Deal with || and && only when there is a full set of symbolics.
1367 if (!lhs || !ssa1 || !ssa2
1368 || (TREE_CODE (TREE_TYPE (lhs)) != BOOLEAN_TYPE)
1369 || (TREE_CODE (TREE_TYPE (ssa1)) != BOOLEAN_TYPE)
1370 || (TREE_CODE (TREE_TYPE (ssa2)) != BOOLEAN_TYPE))
1371 return;
1372
1373 // Now we know its a boolean AND or OR expression with boolean operands.
1374 // Ideally we search dependencies for common names, and see what pops out.
1375 // until then, simply try to resolve direct dependencies.
1376
1377 gimple *ssa1_stmt = SSA_NAME_DEF_STMT (ssa1);
1378 gimple *ssa2_stmt = SSA_NAME_DEF_STMT (ssa2);
1379
1380 range_operator *handler1 = gimple_range_handler (SSA_NAME_DEF_STMT (ssa1));
1381 range_operator *handler2 = gimple_range_handler (SSA_NAME_DEF_STMT (ssa2));
1382
1383 // If either handler is not present, no relation can be found.
1384 if (!handler1 || !handler2)
1385 return;
1386
1387 // Both stmts will need to have 2 ssa names in the stmt.
1388 tree ssa1_dep1 = gimple_range_ssa_p (gimple_range_operand1 (ssa1_stmt));
1389 tree ssa1_dep2 = gimple_range_ssa_p (gimple_range_operand2 (ssa1_stmt));
1390 tree ssa2_dep1 = gimple_range_ssa_p (gimple_range_operand1 (ssa2_stmt));
1391 tree ssa2_dep2 = gimple_range_ssa_p (gimple_range_operand2 (ssa2_stmt));
1392
1393 if (!ssa1_dep1 || !ssa1_dep2 || !ssa2_dep1 || !ssa2_dep2)
1394 return;
1395
1396 // Make sure they are the same dependencies, and detect the order of the
1397 // relationship.
1398 bool reverse_op2 = true;
1399 if (ssa1_dep1 == ssa2_dep1 && ssa1_dep2 == ssa2_dep2)
1400 reverse_op2 = false;
1401 else if (ssa1_dep1 != ssa2_dep2 || ssa1_dep2 != ssa2_dep1)
1402 return;
1403
1404 int_range<2> bool_one (boolean_true_node, boolean_true_node);
1405
1406 relation_kind relation1 = handler1->op1_op2_relation (bool_one);
1407 relation_kind relation2 = handler2->op1_op2_relation (bool_one);
1408 if (relation1 == VREL_NONE || relation2 == VREL_NONE)
1409 return;
1410
1411 if (reverse_op2)
1412 relation2 = relation_negate (relation2);
1413
1414 // x && y is false if the relation intersection of the true cases is NULL.
1415 if (is_and && relation_intersect (relation1, relation2) == VREL_EMPTY)
1416 lhs_range = int_range<2> (boolean_false_node, boolean_false_node);
1417 // x || y is true if the union of the true cases is NO-RELATION..
1418 // ie, one or the other being true covers the full range of possibilties.
1419 else if (!is_and && relation_union (relation1, relation2) == VREL_NONE)
1420 lhs_range = bool_one;
1421 else
1422 return;
1423
1424 range_cast (lhs_range, TREE_TYPE (lhs));
1425 if (dump_file && (dump_flags & TDF_DETAILS))
1426 {
1427 fprintf (dump_file, " Relation adjustment: ");
1428 print_generic_expr (dump_file, ssa1, TDF_SLIM);
1429 fprintf (dump_file, " and ");
1430 print_generic_expr (dump_file, ssa2, TDF_SLIM);
1431 fprintf (dump_file, " combine to produce ");
1432 lhs_range.dump (dump_file);
1433 fputc ('\n', dump_file);
1434 }
1435
1436 return;
1437 }
1438
1439 // Register any outgoing edge relations from a conditional branch.
1440
1441 void
1442 fur_source::register_outgoing_edges (gcond *s, irange &lhs_range, edge e0, edge e1)
1443 {
1444 int_range_max r;
1445 int_range<2> e0_range, e1_range;
1446 tree name;
1447 range_operator *handler;
1448 basic_block bb = gimple_bb (s);
1449
1450 if (e0)
1451 {
1452 // If this edge is never taken, ignore it.
1453 gcond_edge_range (e0_range, e0);
1454 e0_range.intersect (lhs_range);
1455 if (e0_range.undefined_p ())
1456 e0 = NULL;
1457 }
1458
1459
1460 if (e1)
1461 {
1462 // If this edge is never taken, ignore it.
1463 gcond_edge_range (e1_range, e1);
1464 e1_range.intersect (lhs_range);
1465 if (e1_range.undefined_p ())
1466 e1 = NULL;
1467 }
1468
1469 if (!e0 && !e1)
1470 return;
1471
1472 // First, register the gcond itself. This will catch statements like
1473 // if (a_2 < b_5)
1474 tree ssa1 = gimple_range_ssa_p (gimple_range_operand1 (s));
1475 tree ssa2 = gimple_range_ssa_p (gimple_range_operand2 (s));
1476 if (ssa1 && ssa2)
1477 {
1478 handler = gimple_range_handler (s);
1479 gcc_checking_assert (handler);
1480 if (e0)
1481 {
1482 relation_kind relation = handler->op1_op2_relation (e0_range);
1483 if (relation != VREL_NONE)
1484 register_relation (e0, relation, ssa1, ssa2);
1485 }
1486 if (e1)
1487 {
1488 relation_kind relation = handler->op1_op2_relation (e1_range);
1489 if (relation != VREL_NONE)
1490 register_relation (e1, relation, ssa1, ssa2);
1491 }
1492 }
1493
1494 // Outgoing relations of GORI exports require a gori engine.
1495 if (!gori ())
1496 return;
1497
1498 // Now look for other relations in the exports. This will find stmts
1499 // leading to the condition such as:
1500 // c_2 = a_4 < b_7
1501 // if (c_2)
1502 FOR_EACH_GORI_EXPORT_NAME (*(gori ()), bb, name)
1503 {
1504 if (TREE_CODE (TREE_TYPE (name)) != BOOLEAN_TYPE)
1505 continue;
1506 gimple *stmt = SSA_NAME_DEF_STMT (name);
1507 handler = gimple_range_handler (stmt);
1508 if (!handler)
1509 continue;
1510 tree ssa1 = gimple_range_ssa_p (gimple_range_operand1 (stmt));
1511 tree ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt));
1512 if (ssa1 && ssa2)
1513 {
1514 if (e0 && gori ()->outgoing_edge_range_p (r, e0, name, *m_query)
1515 && r.singleton_p ())
1516 {
1517 relation_kind relation = handler->op1_op2_relation (r);
1518 if (relation != VREL_NONE)
1519 register_relation (e0, relation, ssa1, ssa2);
1520 }
1521 if (e1 && gori ()->outgoing_edge_range_p (r, e1, name, *m_query)
1522 && r.singleton_p ())
1523 {
1524 relation_kind relation = handler->op1_op2_relation (r);
1525 if (relation != VREL_NONE)
1526 register_relation (e1, relation, ssa1, ssa2);
1527 }
1528 }
1529 }
1530 }
This page took 0.107339 seconds and 5 git commands to generate.