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

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