Branch data Line data Source code
1 : : /* Gimple range edge functionality.
2 : : Copyright (C) 2020-2025 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 : :
23 : : #include "config.h"
24 : : #include "system.h"
25 : : #include "coretypes.h"
26 : : #include "backend.h"
27 : : #include "tree.h"
28 : : #include "gimple.h"
29 : : #include "ssa.h"
30 : : #include "gimple-pretty-print.h"
31 : : #include "gimple-iterator.h"
32 : : #include "tree-cfg.h"
33 : : #include "gimple-range.h"
34 : : #include "value-range-storage.h"
35 : :
36 : : // If there is a range control statement at the end of block BB, return it.
37 : : // Otherwise return NULL.
38 : :
39 : : gimple *
40 : 221543801 : gimple_outgoing_range_stmt_p (basic_block bb)
41 : : {
42 : 221543801 : gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
43 : 221543801 : if (!gsi_end_p (gsi))
44 : : {
45 : 196500343 : gimple *s = gsi_stmt (gsi);
46 : 196500343 : if (is_a<gcond *> (s) && gimple_range_op_handler::supported_p (s))
47 : 162919796 : return gsi_stmt (gsi);
48 : 34437413 : if (is_a <gswitch *> (s))
49 : 162919796 : return gsi_stmt (gsi);
50 : : }
51 : : return NULL;
52 : : }
53 : :
54 : : // Return a TRUE or FALSE range representing the edge value of a GCOND.
55 : :
56 : : void
57 : 196928851 : gcond_edge_range (irange &r, edge e)
58 : : {
59 : 196928851 : gcc_checking_assert (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE));
60 : 196928851 : if (e->flags & EDGE_TRUE_VALUE)
61 : 95505077 : r = range_true ();
62 : : else
63 : 101423774 : r = range_false ();
64 : 196928851 : }
65 : :
66 : : // Construct a gimple_outgoing_range object. No memory is allocated.
67 : :
68 : 25325506 : gimple_outgoing_range::gimple_outgoing_range (int max_sw_edges)
69 : : {
70 : 25325506 : m_edge_table = NULL;
71 : 25325506 : m_range_allocator = NULL;
72 : 25325506 : m_max_edges = max_sw_edges;
73 : 25325506 : }
74 : :
75 : : // Destruct an edge object, disposing of any memory allocated.
76 : :
77 : 25325506 : gimple_outgoing_range::~gimple_outgoing_range ()
78 : : {
79 : 25325506 : if (m_edge_table)
80 : 53961 : delete m_edge_table;
81 : 25325506 : if (m_range_allocator)
82 : 53961 : delete m_range_allocator;
83 : 25325506 : }
84 : :
85 : : // Set a new switch limit.
86 : :
87 : : void
88 : 0 : gimple_outgoing_range::set_switch_limit (int max_sw_edges)
89 : : {
90 : 0 : m_max_edges = max_sw_edges;
91 : 0 : }
92 : :
93 : : // Get a range for a switch edge E from statement S and return it in R.
94 : : // Use a cached value if it exists, or calculate it if not.
95 : :
96 : : bool
97 : 461222 : gimple_outgoing_range::switch_edge_range (irange &r, gswitch *sw, edge e)
98 : : {
99 : : // ADA currently has cases where the index is 64 bits and the case
100 : : // arguments are 32 bit, causing a trap when we create a case_range.
101 : : // Until this is resolved (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87798)
102 : : // punt on switches where the labels don't match the argument.
103 : 461222 : if (gimple_switch_num_labels (sw) > 1 &&
104 : 461222 : TYPE_PRECISION (TREE_TYPE (CASE_LOW (gimple_switch_label (sw, 1)))) !=
105 : 461222 : TYPE_PRECISION (TREE_TYPE (gimple_switch_index (sw))))
106 : : return false;
107 : :
108 : 461201 : if (!m_edge_table)
109 : 53961 : m_edge_table = new hash_map<edge, vrange_storage *> (n_edges_for_fn (cfun));
110 : 461201 : if (!m_range_allocator)
111 : 53961 : m_range_allocator = new vrange_allocator;
112 : :
113 : 461201 : vrange_storage **val = m_edge_table->get (e);
114 : 461201 : if (!val)
115 : : {
116 : 63698 : calc_switch_ranges (sw);
117 : 63698 : val = m_edge_table->get (e);
118 : 63698 : gcc_checking_assert (val);
119 : : }
120 : 461201 : (*val)->get_vrange (r, TREE_TYPE (gimple_switch_index (sw)));
121 : 461201 : return true;
122 : : }
123 : :
124 : :
125 : : // Calculate all switch edges from SW and cache them in the hash table.
126 : :
127 : : void
128 : 63698 : gimple_outgoing_range::calc_switch_ranges (gswitch *sw)
129 : : {
130 : 63698 : bool existed;
131 : 63698 : unsigned x, lim;
132 : 63698 : lim = gimple_switch_num_labels (sw);
133 : 63698 : tree type = TREE_TYPE (gimple_switch_index (sw));
134 : 63698 : edge default_edge = gimple_switch_default_edge (cfun, sw);
135 : :
136 : : // This should be the first call into this switch.
137 : : //
138 : : // Allocate an int_range_max for the default range case, start with
139 : : // varying and intersect each other case from it.
140 : 63698 : int_range_max default_range (type);
141 : :
142 : 562776 : for (x = 1; x < lim; x++)
143 : : {
144 : 499078 : edge e = gimple_switch_edge (cfun, sw, x);
145 : :
146 : : // If this edge is the same as the default edge, do nothing else.
147 : 499078 : if (e == default_edge)
148 : 31 : continue;
149 : :
150 : 499063 : wide_int low = wi::to_wide (CASE_LOW (gimple_switch_label (sw, x)));
151 : 499063 : wide_int high;
152 : 499063 : tree tree_high = CASE_HIGH (gimple_switch_label (sw, x));
153 : 499063 : if (tree_high)
154 : 35226 : high = wi::to_wide (tree_high);
155 : : else
156 : 463837 : high = low;
157 : :
158 : : // Remove the case range from the default case.
159 : 499063 : int_range_max def_range (type, low, high);
160 : 499063 : range_cast (def_range, type);
161 : : // If all possible values are taken, set default_range to UNDEFINED.
162 : 499063 : if (def_range.varying_p ())
163 : 1 : default_range.set_undefined ();
164 : : else
165 : : {
166 : 499062 : def_range.invert ();
167 : 499062 : default_range.intersect (def_range);
168 : : }
169 : :
170 : : // Create/union this case with anything on else on the edge.
171 : 499063 : int_range_max case_range (type, low, high);
172 : 499063 : range_cast (case_range, type);
173 : 499063 : vrange_storage *&slot = m_edge_table->get_or_insert (e, &existed);
174 : 499063 : if (existed)
175 : : {
176 : : // If this doesn't change the value, move on.
177 : 98935 : int_range_max tmp;
178 : 98935 : slot->get_vrange (tmp, type);
179 : 98935 : if (!case_range.union_ (tmp))
180 : 0 : continue;
181 : 98935 : if (slot->fits_p (case_range))
182 : : {
183 : 16 : slot->set_vrange (case_range);
184 : 16 : continue;
185 : : }
186 : 98935 : }
187 : : // If there was an existing range and it doesn't fit, we lose the memory.
188 : : // It'll get reclaimed when the obstack is freed. This seems less
189 : : // intrusive than allocating max ranges for each case.
190 : 499047 : slot = m_range_allocator->clone (case_range);
191 : 499063 : }
192 : :
193 : 63698 : vrange_storage *&slot = m_edge_table->get_or_insert (default_edge, &existed);
194 : : // This should be the first call into this switch.
195 : 63698 : gcc_checking_assert (!existed);
196 : 63698 : slot = m_range_allocator->clone (default_range);
197 : 63698 : }
198 : :
199 : :
200 : : // Calculate the range forced on on edge E by control flow, return it
201 : : // in R. Return the statement which defines the range, otherwise
202 : : // return NULL
203 : :
204 : : gimple *
205 : 123094246 : gimple_outgoing_range::edge_range_p (irange &r, edge e)
206 : : {
207 : 123094246 : if (single_succ_p (e->src))
208 : : return NULL;
209 : :
210 : : // Determine if there is an outgoing edge.
211 : 82102047 : gimple *s = gimple_outgoing_range_stmt_p (e->src);
212 : 82102047 : if (!s)
213 : : return NULL;
214 : :
215 : 81167384 : if (is_a<gcond *> (s))
216 : : {
217 : 80705922 : gcond_edge_range (r, e);
218 : 80705922 : return s;
219 : : }
220 : :
221 : : // Only process switches if it within the size limit.
222 : 461462 : if (m_max_edges == 0 || (EDGE_COUNT (e->src->succs) > (unsigned)m_max_edges))
223 : : return NULL;
224 : :
225 : 461222 : gcc_checking_assert (is_a<gswitch *> (s));
226 : 461222 : gswitch *sw = as_a<gswitch *> (s);
227 : :
228 : : // Switches can only be integers.
229 : 461222 : if (switch_edge_range (as_a <irange> (r), sw, e))
230 : : return s;
231 : :
232 : : return NULL;
233 : : }
|
