]>
Commit | Line | Data |
---|---|---|
c46b5b0a | 1 | /* Gimple range edge functionality. |
a945c346 | 2 | Copyright (C) 2020-2024 Free Software Foundation, Inc. |
90e88fd3 AM |
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" | |
3ae9def0 | 34 | #include "value-range-storage.h" |
90e88fd3 | 35 | |
c46b5b0a | 36 | // If there is a range control statement at the end of block BB, return it. |
90e88fd3 AM |
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 (gsi)) | |
44 | { | |
45 | gimple *s = gsi_stmt (gsi); | |
51ce0638 | 46 | if (is_a<gcond *> (s) && gimple_range_op_handler::supported_p (s)) |
90e88fd3 | 47 | return gsi_stmt (gsi); |
a9058b08 | 48 | if (is_a <gswitch *> (s)) |
90e88fd3 AM |
49 | return gsi_stmt (gsi); |
50 | } | |
51 | return NULL; | |
52 | } | |
53 | ||
54 | ||
12f0a54b AM |
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) | |
cb779afe | 62 | r = range_true (); |
12f0a54b | 63 | else |
cb779afe | 64 | r = range_false (); |
12f0a54b AM |
65 | } |
66 | ||
67 | ||
3ca950c3 | 68 | gimple_outgoing_range::gimple_outgoing_range (int max_sw_edges) |
90e88fd3 AM |
69 | { |
70 | m_edge_table = NULL; | |
3ca950c3 | 71 | m_max_edges = max_sw_edges; |
e1366a7e | 72 | m_range_allocator = new vrange_allocator; |
90e88fd3 AM |
73 | } |
74 | ||
12f0a54b AM |
75 | |
76 | gimple_outgoing_range::~gimple_outgoing_range () | |
90e88fd3 AM |
77 | { |
78 | if (m_edge_table) | |
79 | delete m_edge_table; | |
3ae9def0 | 80 | delete m_range_allocator; |
90e88fd3 AM |
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 | |
45c8523d | 88 | gimple_outgoing_range::switch_edge_range (irange &r, gswitch *sw, edge e) |
90e88fd3 | 89 | { |
90e88fd3 AM |
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) | |
c46b5b0a | 93 | // punt on switches where the labels don't match the argument. |
90e88fd3 AM |
94 | if (gimple_switch_num_labels (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) | |
e1366a7e | 100 | m_edge_table = new hash_map<edge, vrange_storage *> (n_edges_for_fn (cfun)); |
90e88fd3 | 101 | |
e1366a7e | 102 | vrange_storage **val = m_edge_table->get (e); |
90e88fd3 AM |
103 | if (!val) |
104 | { | |
105 | calc_switch_ranges (sw); | |
106 | val = m_edge_table->get (e); | |
107 | gcc_checking_assert (val); | |
108 | } | |
e1366a7e | 109 | (*val)->get_vrange (r, TREE_TYPE (gimple_switch_index (sw))); |
90e88fd3 AM |
110 | return true; |
111 | } | |
112 | ||
113 | ||
114 | // Calculate all switch edges from SW and cache them in the hash table. | |
115 | ||
116 | void | |
12f0a54b | 117 | gimple_outgoing_range::calc_switch_ranges (gswitch *sw) |
90e88fd3 AM |
118 | { |
119 | bool existed; | |
120 | unsigned x, lim; | |
121 | lim = gimple_switch_num_labels (sw); | |
122 | tree type = TREE_TYPE (gimple_switch_index (sw)); | |
90e88fd3 | 123 | edge default_edge = gimple_switch_default_edge (cfun, sw); |
90e88fd3 | 124 | |
739526a1 AH |
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. | |
4c07e591 | 129 | int_range_max default_range (type); |
90e88fd3 AM |
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 | ||
cb779afe AH |
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 (tree_high); | |
144 | else | |
90e88fd3 AM |
145 | high = low; |
146 | ||
147 | // Remove the case range from the default case. | |
cb779afe | 148 | int_range_max def_range (type, low, high); |
90e88fd3 AM |
149 | range_cast (def_range, type); |
150 | def_range.invert (); | |
4c07e591 | 151 | default_range.intersect (def_range); |
90e88fd3 AM |
152 | |
153 | // Create/union this case with anything on else on the edge. | |
cb779afe | 154 | int_range_max case_range (type, low, high); |
90e88fd3 | 155 | range_cast (case_range, type); |
e1366a7e | 156 | vrange_storage *&slot = m_edge_table->get_or_insert (e, &existed); |
90e88fd3 AM |
157 | if (existed) |
158 | { | |
f3204ce1 | 159 | // If this doesn't change the value, move on. |
e1366a7e AH |
160 | int_range_max tmp; |
161 | slot->get_vrange (tmp, type); | |
162 | if (!case_range.union_ (tmp)) | |
f3204ce1 | 163 | continue; |
90e88fd3 AM |
164 | if (slot->fits_p (case_range)) |
165 | { | |
e1366a7e | 166 | slot->set_vrange (case_range); |
90e88fd3 AM |
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. | |
e1366a7e | 173 | slot = m_range_allocator->clone (case_range); |
90e88fd3 | 174 | } |
739526a1 | 175 | |
e1366a7e | 176 | vrange_storage *&slot = m_edge_table->get_or_insert (default_edge, &existed); |
739526a1 AH |
177 | // This should be the first call into this switch. |
178 | gcc_checking_assert (!existed); | |
e1366a7e | 179 | slot = m_range_allocator->clone (default_range); |
90e88fd3 AM |
180 | } |
181 | ||
182 | ||
183 | // Calculate the range forced on on edge E by control flow, return it | |
c46b5b0a | 184 | // in R. Return the statement which defines the range, otherwise |
90e88fd3 AM |
185 | // return NULL |
186 | ||
187 | gimple * | |
12f0a54b | 188 | gimple_outgoing_range::edge_range_p (irange &r, edge e) |
90e88fd3 | 189 | { |
63c59f05 RS |
190 | if (single_succ_p (e->src)) |
191 | return NULL; | |
192 | ||
90e88fd3 AM |
193 | // Determine if there is an outgoing edge. |
194 | gimple *s = gimple_outgoing_range_stmt_p (e->src); | |
195 | if (!s) | |
196 | return NULL; | |
197 | ||
198 | if (is_a<gcond *> (s)) | |
199 | { | |
12f0a54b | 200 | gcond_edge_range (r, e); |
90e88fd3 AM |
201 | return s; |
202 | } | |
203 | ||
3ca950c3 AM |
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 | ||
90e88fd3 AM |
208 | gcc_checking_assert (is_a<gswitch *> (s)); |
209 | gswitch *sw = as_a<gswitch *> (s); | |
90e88fd3 | 210 | |
45c8523d AH |
211 | // Switches can only be integers. |
212 | if (switch_edge_range (as_a <irange> (r), sw, e)) | |
90e88fd3 AM |
213 | return s; |
214 | ||
215 | return NULL; | |
216 | } |