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