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