1/* Code for GIMPLE range related routines.
2 Copyright (C) 2019-2024 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@redhat.com>.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 3, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "backend.h"
26#include "insn-codes.h"
27#include "tree.h"
28#include "gimple.h"
29#include "ssa.h"
30#include "gimple-pretty-print.h"
31#include "optabs-tree.h"
32#include "gimple-iterator.h"
33#include "gimple-fold.h"
34#include "wide-int.h"
35#include "fold-const.h"
36#include "case-cfn-macros.h"
37#include "omp-general.h"
38#include "cfgloop.h"
39#include "tree-ssa-loop.h"
40#include "tree-scalar-evolution.h"
41#include "langhooks.h"
42#include "vr-values.h"
43#include "range.h"
44#include "value-query.h"
45#include "gimple-range-op.h"
46#include "gimple-range.h"
47#include "cgraph.h"
48#include "alloc-pool.h"
49#include "symbol-summary.h"
50#include "ipa-utils.h"
51#include "sreal.h"
52#include "ipa-cp.h"
53#include "ipa-prop.h"
54// Construct a fur_source, and set the m_query field.
55
56fur_source::fur_source (range_query *q)
57{
58 if (q)
59 m_query = q;
60 else
61 m_query = get_range_query (cfun);
62 m_gori = NULL;
63}
64
65// Invoke range_of_expr on EXPR.
66
67bool
68fur_source::get_operand (vrange &r, tree expr)
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
76bool
77fur_source::get_phi_operand (vrange &r, tree expr, edge e)
78{
79 return m_query->range_on_edge (r, e, expr);
80}
81
82// Default is no relation.
83
84relation_kind
85fur_source::query_relation (tree op1 ATTRIBUTE_UNUSED,
86 tree op2 ATTRIBUTE_UNUSED)
87{
88 return VREL_VARYING;
89}
90
91// Default registers nothing.
92
93void
94fur_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
103void
104fur_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
113class fur_edge : public fur_source
114{
115public:
116 fur_edge (edge e, range_query *q = NULL);
117 virtual bool get_operand (vrange &r, tree expr) override;
118 virtual bool get_phi_operand (vrange &r, tree expr, edge e) override;
119private:
120 edge m_edge;
121};
122
123// Instantiate an edge based fur_source.
124
125inline
126fur_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
133bool
134fur_edge::get_operand (vrange &r, tree expr)
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
142bool
143fur_edge::get_phi_operand (vrange &r, tree expr, edge e)
144{
145 // Edge to edge recalculations not supported yet, until we sort it out.
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
152fur_stmt::fur_stmt (gimple *s, range_query *q) : fur_source (q)
153{
154 m_stmt = s;
155}
156
157// Retrieve range of EXPR as it occurs as a use on stmt M_STMT.
158
159bool
160fur_stmt::get_operand (vrange &r, tree expr)
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
168bool
169fur_stmt::get_phi_operand (vrange &r, tree expr, edge e)
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
178relation_kind
179fur_stmt::query_relation (tree op1, tree op2)
180{
181 return m_query->query_relation (s: m_stmt, ssa1: op1, ssa2: op2);
182}
183
184// Instantiate a stmt based fur_source with a GORI object.
185
186
187fur_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
200void
201fur_depend::register_relation (gimple *s, relation_kind k, tree op1, tree op2)
202{
203 if (m_oracle)
204 m_oracle->register_stmt (s, k, op1, op2);
205}
206
207// Register a relation on an edge if there is an oracle.
208
209void
210fur_depend::register_relation (edge e, relation_kind k, tree op1, tree op2)
211{
212 if (m_oracle)
213 m_oracle->register_edge (e, k, op1, op2);
214}
215
216// This version of fur_source will pick a range up from a list of ranges
217// supplied by the caller.
218
219class fur_list : public fur_source
220{
221public:
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);
225 virtual bool get_operand (vrange &r, tree expr) override;
226 virtual bool get_phi_operand (vrange &r, tree expr, edge e) override;
227private:
228 vrange *m_local[2];
229 vrange **m_list;
230 unsigned m_index;
231 unsigned m_limit;
232};
233
234// One range supplied for unary operations.
235
236fur_list::fur_list (vrange &r1, range_query *q) : fur_source (q)
237{
238 m_list = m_local;
239 m_index = 0;
240 m_limit = 1;
241 m_local[0] = &r1;
242}
243
244// Two ranges supplied for binary operations.
245
246fur_list::fur_list (vrange &r1, vrange &r2, range_query *q) : fur_source (q)
247{
248 m_list = m_local;
249 m_index = 0;
250 m_limit = 2;
251 m_local[0] = &r1;
252 m_local[1] = &r2;
253}
254
255// Arbitrary number of ranges in a vector.
256
257fur_list::fur_list (unsigned num, vrange **list, range_query *q)
258 : fur_source (q)
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
267bool
268fur_list::get_operand (vrange &r, tree expr)
269{
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)
272 return m_query->range_of_expr (r, expr);
273 r = *m_list[m_index++];
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.
279bool
280fur_list::get_phi_operand (vrange &r, tree expr, edge e ATTRIBUTE_UNUSED)
281{
282 return get_operand (r, expr);
283}
284
285// Fold stmt S into range R using R1 as the first operand.
286
287bool
288fold_range (vrange &r, gimple *s, vrange &r1, range_query *q)
289{
290 fold_using_range f;
291 fur_list src (r1, q);
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
297bool
298fold_range (vrange &r, gimple *s, vrange &r1, vrange &r2, range_query *q)
299{
300 fold_using_range f;
301 fur_list src (r1, r2, q);
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
308bool
309fold_range (vrange &r, gimple *s, unsigned num_elements, vrange **vector,
310 range_query *q)
311{
312 fold_using_range f;
313 fur_list src (num_elements, vector, q);
314 return f.fold_stmt (r, s, src);
315}
316
317// Fold stmt S into range R using range query Q.
318
319bool
320fold_range (vrange &r, gimple *s, range_query *q)
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
329bool
330fold_range (vrange &r, gimple *s, edge on_edge, range_query *q)
331{
332 fold_using_range f;
333 fur_edge src (on_edge, q);
334 return f.fold_stmt (r, s, src);
335}
336
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
341class fur_relation : public fur_stmt
342{
343public:
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;
350private:
351 relation_kind def_op1, def_op2, op1_op2;
352};
353
354fur_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
361relation_trio
362fur_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
369void
370fur_relation::register_relation (edge, relation_kind, tree, tree)
371{
372}
373
374// Register relation K between OP1 and OP2 on STMT.
375
376void
377fur_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 (g: stmt))
384 {
385 case GIMPLE_COND:
386 a1 = gimple_cond_lhs (gs: stmt);
387 a2 = gimple_cond_rhs (gs: stmt);
388 break;
389 case GIMPLE_ASSIGN:
390 a1 = gimple_assign_rhs1 (gs: stmt);
391 if (gimple_num_ops (gs: stmt) >= 3)
392 a2 = gimple_assign_rhs2 (gs: 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 (r: k);
410 else if (op1 == a2)
411 def_op2 = relation_swap (r: 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 (r: k);
419 }
420}
421
422// Return the relation trio for stmt S using query Q.
423
424relation_trio
425fold_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 (exp: gimple_get_lhs (s));
430 if (lhs)
431 {
432 Value_Range vr(TREE_TYPE (lhs));
433 if (f.fold_stmt (r&: vr, s, src))
434 return src.trio ();
435 }
436 return TRIO_VARYING;
437}
438
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
451static void
452adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt)
453{
454 tree op0 = gimple_assign_rhs1 (gs: diff_stmt);
455 tree op1 = gimple_assign_rhs2 (gs: 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 (gs: 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 (gs: call, index: 0))
471 && integer_zerop (gimple_call_arg (gs: call, index: 1)))
472 {
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));
477 }
478}
479
480// Adjust the range for an IMAGPART_EXPR.
481
482static void
483adjust_imagpart_expr (vrange &res, const gimple *stmt)
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 (gs: def_stmt) && gimple_call_internal_p (gs: def_stmt))
492 {
493 switch (gimple_call_internal_fn (gs: def_stmt))
494 {
495 case IFN_ADD_OVERFLOW:
496 case IFN_SUB_OVERFLOW:
497 case IFN_MUL_OVERFLOW:
498 case IFN_UADDC:
499 case IFN_USUBC:
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 }
513 if (is_gimple_assign (gs: def_stmt)
514 && gimple_assign_rhs_code (gs: def_stmt) == COMPLEX_CST)
515 {
516 tree cst = gimple_assign_rhs1 (gs: def_stmt);
517 if (TREE_CODE (cst) == COMPLEX_CST
518 && TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) == INTEGER_TYPE)
519 {
520 wide_int w = wi::to_wide (TREE_IMAGPART (cst));
521 int_range<1> imag (TREE_TYPE (TREE_IMAGPART (cst)), w, w);
522 res.intersect (imag);
523 }
524 }
525}
526
527// Adjust the range for a REALPART_EXPR.
528
529static void
530adjust_realpart_expr (vrange &res, const gimple *stmt)
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
541 if (is_gimple_assign (gs: def_stmt)
542 && gimple_assign_rhs_code (gs: def_stmt) == COMPLEX_CST)
543 {
544 tree cst = gimple_assign_rhs1 (gs: def_stmt);
545 if (TREE_CODE (cst) == COMPLEX_CST
546 && TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) == INTEGER_TYPE)
547 {
548 wide_int imag = wi::to_wide (TREE_REALPART (cst));
549 int_range<2> tmp (TREE_TYPE (TREE_REALPART (cst)), imag, imag);
550 res.intersect (tmp);
551 }
552 }
553}
554
555// This function looks for situations when walking the use/def chains
556// may provide additional contextual range information not exposed on
557// this statement.
558
559static void
560gimple_range_adjustment (vrange &res, const gimple *stmt)
561{
562 switch (gimple_expr_code (stmt))
563 {
564 case POINTER_DIFF_EXPR:
565 adjust_pointer_diff_expr (res&: as_a <irange> (v&: res), diff_stmt: stmt);
566 return;
567
568 case IMAGPART_EXPR:
569 adjust_imagpart_expr (res, stmt);
570 return;
571
572 case REALPART_EXPR:
573 adjust_realpart_expr (res, stmt);
574 return;
575
576 default:
577 break;
578 }
579}
580
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
586bool
587fold_using_range::fold_stmt (vrange &r, gimple *s, fur_source &src, tree name)
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 (g: s) == GIMPLE_ASSIGN
599 && gimple_assign_rhs_code (gs: s) == ADDR_EXPR)
600 return range_of_address (r&: as_a <irange> (v&: r), s, src);
601
602 gimple_range_op_handler handler (s);
603 if (handler)
604 res = range_of_range_op (r, handler, src);
605 else if (is_a<gphi *>(p: s))
606 res = range_of_phi (r, phi: as_a<gphi *> (p: s), src);
607 else if (is_a<gcall *>(p: s))
608 res = range_of_call (r, call: as_a<gcall *> (p: s), src);
609 else if (is_a<gassign *> (p: s) && gimple_assign_rhs_code (gs: s) == COND_EXPR)
610 res = range_of_cond_expr (r, cond: as_a<gassign *> (p: s), src);
611
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
620 if (!res)
621 {
622 // If no name specified or range is unsupported, bail.
623 if (!name || !gimple_range_ssa_p (exp: name))
624 return false;
625 // We don't understand the stmt, so return the global range.
626 gimple_range_global (v&: r, name);
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
646bool
647fold_using_range::range_of_range_op (vrange &r,
648 gimple_range_op_handler &handler,
649 fur_source &src)
650{
651 gcc_checking_assert (handler);
652 gimple *s = handler.stmt ();
653 tree type = gimple_range_type (s);
654 if (!type)
655 return false;
656
657 tree lhs = handler.lhs ();
658 tree op1 = handler.operand1 ();
659 tree op2 = handler.operand2 ();
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, lh: r1, rh: r1))
666 r.set_varying (type);
667 return true;
668 }
669
670 Value_Range range1 (TREE_TYPE (op1));
671 Value_Range range2 (op2 ? TREE_TYPE (op2) : TREE_TYPE (op1));
672
673 if (src.get_operand (r&: range1, expr: op1))
674 {
675 if (!op2)
676 {
677 // Fold range, and register any dependency if available.
678 Value_Range r2 (type);
679 r2.set_varying (type);
680 if (!handler.fold_range (r, type, lh: range1, rh: r2))
681 r.set_varying (type);
682 if (lhs && gimple_range_ssa_p (exp: op1))
683 {
684 if (src.gori ())
685 src.gori ()->register_dependency (name: lhs, ssa1: op1);
686 relation_kind rel;
687 rel = handler.lhs_op1_relation (lhs: r, op1: range1, op2: range1);
688 if (rel != VREL_VARYING)
689 src.register_relation (s, k: rel, op1: lhs, op2: op1);
690 }
691 }
692 else if (src.get_operand (r&: range2, expr: op2))
693 {
694 relation_kind rel = src.query_relation (op1, op2);
695 if (dump_file && (dump_flags & TDF_DETAILS) && rel != VREL_VARYING)
696 {
697 fprintf (stream: dump_file, format: " folding with relation ");
698 print_generic_expr (dump_file, op1, TDF_SLIM);
699 print_relation (f: dump_file, rel);
700 print_generic_expr (dump_file, op2, TDF_SLIM);
701 fputc (c: '\n', stream: dump_file);
702 }
703 // Fold range, and register any dependency if available.
704 if (!handler.fold_range (r, type, lh: range1, rh: range2,
705 relation_trio::op1_op2 (k: rel)))
706 r.set_varying (type);
707 if (irange::supports_p (type))
708 relation_fold_and_or (lhs_range&: as_a <irange> (v&: r), s, src, op1&: range1, op2&: range2);
709 if (lhs)
710 {
711 if (src.gori ())
712 {
713 src.gori ()->register_dependency (name: lhs, ssa1: op1);
714 src.gori ()->register_dependency (name: lhs, ssa1: op2);
715 }
716 if (gimple_range_ssa_p (exp: op1))
717 {
718 rel = handler.lhs_op1_relation (lhs: r, op1: range1, op2: range2, rel);
719 if (rel != VREL_VARYING)
720 src.register_relation (s, k: rel, op1: lhs, op2: op1);
721 }
722 if (gimple_range_ssa_p (exp: op2))
723 {
724 rel = handler.lhs_op2_relation (lhs: r, op1: range1, op2: range2, rel);
725 if (rel != VREL_VARYING)
726 src.register_relation (s, k: rel, op1: lhs, op2);
727 }
728 }
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 *> (p: s) && gimple_bb (g: s))
732 {
733 basic_block bb = gimple_bb (g: s);
734 edge e0 = EDGE_SUCC (bb, 0);
735 edge e1 = EDGE_SUCC (bb, 1);
736
737 if (!single_pred_p (bb: e0->dest))
738 e0 = NULL;
739 if (!single_pred_p (bb: e1->dest))
740 e1 = NULL;
741 src.register_outgoing_edges (as_a<gcond *> (p: s),
742 lhs_range&: as_a <irange> (v&: r), e0, e1);
743 }
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 (res&: r, stmt: 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
759bool
760fold_using_range::range_of_address (irange &r, gimple *stmt, fur_source &src)
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 (gs: 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 (exp: ssa) && src.gori ())
783 src.gori ()->register_dependency (name: lhs, ssa1: ssa);
784 src.get_operand (r, expr: 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 (a: wi::to_poly_wide (t: offset),
794 sgn: 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))
801 return true;
802 else if (flag_delete_null_pointer_checks
803 && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)))
804 {
805 /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
806 allow going from non-NULL pointer to NULL. */
807 if (r.undefined_p ()
808 || !r.contains_p (wi::zero (TYPE_PRECISION (TREE_TYPE (expr)))))
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. */
813 r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
814 return true;
815 }
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 {
825 r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
826 return true;
827 }
828 r.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt)));
829 return true;
830 }
831
832 // Handle "= &a".
833 if (tree_single_nonzero_warnv_p (expr, &strict_overflow_p))
834 {
835 r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
836 return true;
837 }
838
839 // Otherwise return varying.
840 r.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt)));
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
847bool
848fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src)
849{
850 tree phi_def = gimple_phi_result (gs: phi);
851 tree type = gimple_range_type (s: phi);
852 Value_Range arg_range (type);
853 Value_Range equiv_range (type);
854 unsigned x;
855
856 if (!type)
857 return false;
858
859 // Track if all executable arguments are the same.
860 tree single_arg = NULL_TREE;
861 bool seen_arg = false;
862
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 (gs: phi); x++)
866 {
867 tree arg = gimple_phi_arg_def (gs: phi, index: x);
868 // An argument that is the same as the def provides no new range.
869 if (arg == phi_def)
870 continue;
871
872 edge e = gimple_phi_arg_edge (phi, i: x);
873
874 // Get the range of the argument on its edge.
875 src.get_phi_operand (r&: arg_range, expr: arg, e);
876
877 if (!arg_range.undefined_p ())
878 {
879 // Register potential dependencies for stale value tracking.
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.
883 if (src.query ()->query_relation (e, ssa1: arg, ssa2: phi_def, get_range: false) == VREL_EQ)
884 equiv_range.union_(r: arg_range);
885 else
886 r.union_ (arg_range);
887
888 if (gimple_range_ssa_p (exp: arg) && src.gori ())
889 src.gori ()->register_dependency (name: phi_def, ssa1: arg);
890 }
891
892 // Track if all arguments are the same.
893 if (!seen_arg)
894 {
895 seen_arg = true;
896 single_arg = arg;
897 }
898 else if (single_arg != arg)
899 single_arg = NULL_TREE;
900
901 // Once the value reaches varying, stop looking.
902 if (r.varying_p () && single_arg == NULL_TREE)
903 break;
904 }
905
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 (exp: 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 (g: phi);
921 if (!dom_info_available_p (CDI_DOMINATORS))
922 single_arg = NULL;
923 else
924 for (x = 0; x < gimple_phi_num_args (gs: phi); x++)
925 if (gimple_phi_arg_def (gs: phi, index: x) == single_arg
926 && dominated_by_p (CDI_DOMINATORS,
927 gimple_phi_arg_edge (phi, i: x)->src,
928 bb))
929 {
930 single_arg = NULL;
931 break;
932 }
933 if (single_arg)
934 src.register_relation (s: phi, k: VREL_EQ, op1: phi_def, op2: single_arg);
935 }
936 else if (src.get_operand (r&: arg_range, expr: 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 }
946
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 (stream: dump_file, format: "PHI GROUP query for ");
957 print_generic_expr (dump_file, phi_def, TDF_SLIM);
958 fprintf (stream: dump_file, format: " found : ");
959 g->range ().dump (dump_file);
960 fprintf (stream: dump_file, format: " 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 (stream: dump_file, format: " to :");
967 r.dump (dump_file);
968 fprintf (stream: dump_file, format: "\n");
969 }
970 }
971 }
972
973 // If SCEV is available, query if this PHI has any known values.
974 if (scev_initialized_p ()
975 && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
976 {
977 class loop *l = loop_containing_stmt (stmt: phi);
978 if (l && loop_outer (loop: l))
979 {
980 Value_Range loop_range (type);
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 {
986 fprintf (stream: dump_file, format: "Loops range found for ");
987 print_generic_expr (dump_file, phi_def, TDF_SLIM);
988 fprintf (stream: dump_file, format: ": ");
989 loop_range.dump (dump_file);
990 fprintf (stream: dump_file, format: " and calculated range :");
991 r.dump (dump_file);
992 fprintf (stream: dump_file, format: "\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
1005bool
1006fold_using_range::range_of_call (vrange &r, gcall *call, fur_source &)
1007{
1008 tree type = gimple_range_type (s: call);
1009 if (!type)
1010 return false;
1011
1012 tree lhs = gimple_call_lhs (gs: call);
1013 bool strict_overflow_p;
1014
1015 if (gimple_stmt_nonnegative_warnv_p (call, &strict_overflow_p))
1016 r.set_nonnegative (type);
1017 else if (gimple_call_nonnull_result_p (call)
1018 || gimple_call_nonnull_arg (call))
1019 r.set_nonzero (type);
1020 else
1021 r.set_varying (type);
1022
1023 tree callee = gimple_call_fndecl (gs: 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 (range&: val, decl: callee))
1029 {
1030 r.intersect (val);
1031 if (dump_file && (dump_flags & TDF_DETAILS))
1032 {
1033 fprintf (stream: dump_file, format: "Using return value range of ");
1034 print_generic_expr (dump_file, callee, TDF_SLIM);
1035 fprintf (stream: dump_file, format: ": ");
1036 val.dump (dump_file);
1037 fprintf (stream: dump_file, format: "\n");
1038 }
1039 }
1040 }
1041
1042 // If there is an LHS, intersect that with what is known.
1043 if (lhs)
1044 {
1045 Value_Range def (TREE_TYPE (lhs));
1046 gimple_range_global (v&: def, name: lhs);
1047 r.intersect (def);
1048 }
1049 return true;
1050}
1051
1052// Calculate a range for COND_EXPR statement S and return it in R.
1053// If a range cannot be calculated, return false.
1054
1055bool
1056fold_using_range::range_of_cond_expr (vrange &r, gassign *s, fur_source &src)
1057{
1058 tree cond = gimple_assign_rhs1 (gs: s);
1059 tree op1 = gimple_assign_rhs2 (gs: s);
1060 tree op2 = gimple_assign_rhs3 (gs: s);
1061
1062 tree type = gimple_range_type (s);
1063 if (!type)
1064 return false;
1065
1066 Value_Range range1 (TREE_TYPE (op1));
1067 Value_Range range2 (TREE_TYPE (op2));
1068 Value_Range cond_range (TREE_TYPE (cond));
1069 gcc_checking_assert (gimple_assign_rhs_code (s) == COND_EXPR);
1070 gcc_checking_assert (range_compatible_p (TREE_TYPE (op1), TREE_TYPE (op2)));
1071 src.get_operand (r&: cond_range, expr: cond);
1072 src.get_operand (r&: range1, expr: op1);
1073 src.get_operand (r&: range2, expr: op2);
1074
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 (r1&: range1, r2&: range2, s, cond, op1, op2, src))
1078 if (dump_file && (dump_flags & TDF_DETAILS))
1079 {
1080 fprintf (stream: dump_file, format: "Possible COND_EXPR adjustment. Range op1 : ");
1081 range1.dump(dump_file);
1082 fprintf (stream: dump_file, format: " and Range op2: ");
1083 range2.dump(dump_file);
1084 fprintf (stream: dump_file, format: "\n");
1085 }
1086
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 }
1101 gcc_checking_assert (r.undefined_p ()
1102 || range_compatible_p (r.type (), type));
1103 return true;
1104}
1105
1106// If SCEV has any information about phi node NAME, return it as a range in R.
1107
1108void
1109fold_using_range::range_of_ssa_name_with_loop_info (vrange &r, tree name,
1110 class loop *l, gphi *phi,
1111 fur_source &src)
1112{
1113 gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
1114 if (!range_of_var_in_loop (r, var: name, l, phi, src.query ()))
1115 r.set_varying (TREE_TYPE (name));
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
1127void
1128fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s,
1129 fur_source &src, vrange &op1,
1130 vrange &op2)
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 (stmt: 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
1144 gimple_range_op_handler handler (s);
1145 tree lhs = handler.lhs ();
1146 tree ssa1 = gimple_range_ssa_p (exp: handler.operand1 ());
1147 tree ssa2 = gimple_range_ssa_p (exp: handler.operand2 ());
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
1160 gimple *ssa1_stmt = SSA_NAME_DEF_STMT (ssa1);
1161 gimple *ssa2_stmt = SSA_NAME_DEF_STMT (ssa2);
1162
1163 gimple_range_op_handler handler1 (ssa1_stmt);
1164 gimple_range_op_handler handler2 (ssa2_stmt);
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.
1171 tree ssa1_dep1 = gimple_range_ssa_p (exp: handler1.operand1 ());
1172 tree ssa1_dep2 = gimple_range_ssa_p (exp: handler1.operand2 ());
1173 tree ssa2_dep1 = gimple_range_ssa_p (exp: handler2.operand1 ());
1174 tree ssa2_dep2 = gimple_range_ssa_p (exp: handler2.operand2 ());
1175
1176 if (!ssa1_dep1 || !ssa1_dep2 || !ssa2_dep1 || !ssa2_dep2)
1177 return;
1178
1179 if (HONOR_NANS (TREE_TYPE (ssa1_dep1)))
1180 return;
1181
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
1190 int_range<2> bool_one = range_true ();
1191 relation_kind relation1 = handler1.op1_op2_relation (lhs: bool_one, op1, op2);
1192 relation_kind relation2 = handler2.op1_op2_relation (lhs: bool_one, op1, op2);
1193 if (relation1 == VREL_VARYING || relation2 == VREL_VARYING)
1194 return;
1195
1196 if (reverse_op2)
1197 relation2 = relation_negate (r: relation2);
1198
1199 // x && y is false if the relation intersection of the true cases is NULL.
1200 if (is_and && relation_intersect (r1: relation1, r2: relation2) == VREL_UNDEFINED)
1201 lhs_range = range_false (boolean_type_node);
1202 // x || y is true if the union of the true cases is NO-RELATION..
1203 // ie, one or the other being true covers the full range of possibilities.
1204 else if (!is_and && relation_union (r1: relation1, r2: relation2) == VREL_VARYING)
1205 lhs_range = bool_one;
1206 else
1207 return;
1208
1209 range_cast (r&: lhs_range, TREE_TYPE (lhs));
1210 if (dump_file && (dump_flags & TDF_DETAILS))
1211 {
1212 fprintf (stream: dump_file, format: " Relation adjustment: ");
1213 print_generic_expr (dump_file, ssa1, TDF_SLIM);
1214 fprintf (stream: dump_file, format: " and ");
1215 print_generic_expr (dump_file, ssa2, TDF_SLIM);
1216 fprintf (stream: dump_file, format: " combine to produce ");
1217 lhs_range.dump (dump_file);
1218 fputc (c: '\n', stream: dump_file);
1219 }
1220
1221 return;
1222}
1223
1224// Register any outgoing edge relations from a conditional branch.
1225
1226void
1227fur_source::register_outgoing_edges (gcond *s, irange &lhs_range,
1228 edge e0, edge e1)
1229{
1230 int_range<2> e0_range, e1_range;
1231 tree name;
1232 basic_block bb = gimple_bb (g: s);
1233
1234 gimple_range_op_handler handler (s);
1235 if (!handler)
1236 return;
1237
1238 if (e0)
1239 {
1240 // If this edge is never taken, ignore it.
1241 gcond_edge_range (r&: e0_range, e: e0);
1242 e0_range.intersect (lhs_range);
1243 if (e0_range.undefined_p ())
1244 e0 = NULL;
1245 }
1246
1247 if (e1)
1248 {
1249 // If this edge is never taken, ignore it.
1250 gcond_edge_range (r&: e1_range, e: e1);
1251 e1_range.intersect (lhs_range);
1252 if (e1_range.undefined_p ())
1253 e1 = NULL;
1254 }
1255
1256 if (!e0 && !e1)
1257 return;
1258
1259 // First, register the gcond itself. This will catch statements like
1260 // if (a_2 < b_5)
1261 tree ssa1 = gimple_range_ssa_p (exp: handler.operand1 ());
1262 tree ssa2 = gimple_range_ssa_p (exp: handler.operand2 ());
1263 Value_Range r1,r2;
1264 if (ssa1 && ssa2)
1265 {
1266 r1.set_varying (TREE_TYPE (ssa1));
1267 r2.set_varying (TREE_TYPE (ssa2));
1268 if (e0)
1269 {
1270 relation_kind relation = handler.op1_op2_relation (lhs: e0_range, op1: r1, op2: r2);
1271 if (relation != VREL_VARYING)
1272 register_relation (e: e0, k: relation, op1: ssa1, op2: ssa2);
1273 }
1274 if (e1)
1275 {
1276 relation_kind relation = handler.op1_op2_relation (lhs: e1_range, op1: r1, op2: r2);
1277 if (relation != VREL_VARYING)
1278 register_relation (e: e1, k: relation, op1: ssa1, op2: ssa2);
1279 }
1280 }
1281
1282 // Outgoing relations of GORI exports require a gori engine.
1283 if (!gori ())
1284 return;
1285
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)
1290 FOR_EACH_GORI_EXPORT_NAME (*(gori ()), bb, name)
1291 {
1292 if (TREE_CODE (TREE_TYPE (name)) != BOOLEAN_TYPE)
1293 continue;
1294 gimple *stmt = SSA_NAME_DEF_STMT (name);
1295 gimple_range_op_handler handler (stmt);
1296 if (!handler)
1297 continue;
1298 tree ssa1 = gimple_range_ssa_p (exp: handler.operand1 ());
1299 tree ssa2 = gimple_range_ssa_p (exp: handler.operand2 ());
1300 Value_Range r (TREE_TYPE (name));
1301 if (ssa1 && ssa2)
1302 {
1303 r1.set_varying (TREE_TYPE (ssa1));
1304 r2.set_varying (TREE_TYPE (ssa2));
1305 if (e0 && gori ()->outgoing_edge_range_p (r, e: e0, name, q&: *m_query)
1306 && r.singleton_p ())
1307 {
1308 relation_kind relation = handler.op1_op2_relation (lhs: r, op1: r1, op2: r2);
1309 if (relation != VREL_VARYING)
1310 register_relation (e: e0, k: relation, op1: ssa1, op2: ssa2);
1311 }
1312 if (e1 && gori ()->outgoing_edge_range_p (r, e: e1, name, q&: *m_query)
1313 && r.singleton_p ())
1314 {
1315 relation_kind relation = handler.op1_op2_relation (lhs: r, op1: r1, op2: r2);
1316 if (relation != VREL_VARYING)
1317 register_relation (e: e1, k: relation, op1: ssa1, op2: ssa2);
1318 }
1319 }
1320 }
1321}
1322

source code of gcc/gimple-range-fold.cc